Abstract
We give the first nontrivial worst-case results for dynamic versions of various basic geometric optimization and measure problems under the semi-online model, where during the insertion of an object we are told when the object is to be deleted. Problems that we can solve with sublinear update time include the Hausdorff distance of two point sets, discrete 1-center, largest empty circle, convex hull volume in three dimensions, volume of the union of axis-parallel cubes, and minimum enclosing rectangle. The decision versions of the Hausdorff distance and discrete 1-center problems can be solved fully dynamically. Some applications are mentioned.
Original language | English (US) |
---|---|
Pages (from-to) | 700-716 |
Number of pages | 17 |
Journal | SIAM Journal on Computing |
Volume | 32 |
Issue number | 3 |
DOIs | |
State | Published - Mar 2003 |
Externally published | Yes |
Keywords
- Computational geometry
- Dynamic data structures
ASJC Scopus subject areas
- General Computer Science
- General Mathematics