Semi-online maintenance of geometric optima and measures

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)700-716
Number of pages17
JournalSIAM Journal on Computing
Volume32
Issue number3
DOIs
StatePublished - Mar 2003
Externally publishedYes

Keywords

  • Computational geometry
  • Dynamic data structures

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Semi-online maintenance of geometric optima and measures'. Together they form a unique fingerprint.

Cite this