Semi-online maintenance of geometric optima and measures

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages474-483
Number of pages10
ISBN (Electronic)089871513X
StatePublished - Jan 1 2002
Externally publishedYes
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Other

Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/TerritoryUnited States
CitySan Francisco
Period1/6/021/8/02

ASJC Scopus subject areas

  • Software
  • 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