Semi-Online Maintenance of Geometric Optima and Measures
Author:
- Timothy M. ChanTCTimothy M. Chan
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 32 (3) , 700-716
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.Keywords
This publication has 25 references indexed in Scilit:
- Geometric Pattern Matching in d -Dimensional SpaceDiscrete & Computational Geometry, 1999
- The Discrete 2-Center ProblemDiscrete & Computational Geometry, 1998
- Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance FunctionsDiscrete & Computational Geometry, 1998
- Almost optimal set covers in finite VC-dimensionDiscrete & Computational Geometry, 1995
- Dynamic half-space range reporting and its applicationsAlgorithmica, 1995
- On range searching with semialgebraic setsDiscrete & Computational Geometry, 1994
- Dynamic Three-Dimensional Linear ProgrammingINFORMS Journal on Computing, 1992
- Dynamic algorithms in computational geometryProceedings of the IEEE, 1992
- Maintenance of geometric extremaJournal of the ACM, 1991
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980