| Abbreviated title. Maintenance of Geometric Optima and Measures (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| We give the rst 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 Hausdor 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 Hausdor distance and discrete 1-center problems can be solved fully dynamically. Some applications are mentioned. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||