On maintaining the width and diameter of a planar point-set online

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

1 Scopus citations

Abstract

Efficient online algorithms are presented for maintaining the (almost-exact) width and diameter of a dynamic planar point-set, 5. Let n be the number of points currently in S, let W and D denote the width and diameter of S, respectively, and let α and β be positive, integer-valued parameters. The algorithm for the width problem uses O(αn) space, supports updates in O(αlog2 n) time, and reports in O(αlog2 n) time an approximation, Ŵ, to the width such that Ŵ/W ≤ √l + tan2 π/4α. The algorithm for the diameter problem uses O(βn) space, supports updates in O(βlogn) time, and reports in O(βn) time an approximation, D, to the diameter such that (formula presented). Thus, for instance, even for a as small as 5, Ŵ/W ≤ 1.01, and for β as small as 11, D/D ≥ .99. All bounds stated are worst-case. Both algorithms, but especially the one for the diameter problem, use well-understood data structures and should be simple to implement. The diameter result yields a fast implementation of the greedy heuristic for maximum-weight Euclidean matching and an efficient online algorithm to maintain approximate convex hulls in the plane.

Original languageEnglish (US)
Title of host publicationISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings
EditorsR.C.T. Lee, Wen-Lian Hsu
PublisherSpringer- Verlag
Pages137-149
Number of pages13
ISBN (Print)9783540549451
DOIs
StatePublished - Jan 1 1991
Event2nd Annual International Symposium on Algorithms, ISA 1991 - Taipei, China
Duration: Dec 16 1991Dec 18 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume557 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd Annual International Symposium on Algorithms, ISA 1991
CountryChina
CityTaipei
Period12/16/9112/18/91

Fingerprint Dive into the research topics of 'On maintaining the width and diameter of a planar point-set online'. Together they form a unique fingerprint.

  • Cite this

    Janardan, R. (1991). On maintaining the width and diameter of a planar point-set online. In R. C. T. Lee, & W-L. Hsu (Eds.), ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings (pp. 137-149). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 557 LNCS). Springer- Verlag. https://doi.org/10.1007/3-540-54945-5_57