Scaling and related techniques for geometry problems

Harold N. Gabow, Jon Louis Bentley, Robert E. Tarjan

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

343 Scopus citations

Abstract

Three techniques in computational geometry are explored: Scaling solves a problem by viewing it at increasing levels of numerical precision; acHvat/ovt is a • restricted type of update operation, useful in sweep algorithms; the CaTtex'hzR tree is a data structure for problems involving maximums and minimums. These techniques solve the minimum spanning tree problem in R and ] in O(zz(lg n)rlg lg n) time and O(n) space, where for Rk∞ and k ≥3, r =k-2; for Rk1, r = 1,2,4 for k =3,4,5 and r =k for k >5. Other problems solved include Rk1 and Rk all nearest neighbors, post office and maximum spanning tree; Rk maxima, Rk rectangle searching problems, and Zpk all nearest neighbors (1≤p≤∞).

Original languageEnglish (US)
Title of host publicationProceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984
PublisherAssociation for Computing Machinery
Pages135-143
Number of pages9
ISBN (Electronic)0897911334
DOIs
StatePublished - Dec 1 1984
Externally publishedYes
Event16th Annual ACM Symposium on Theory of Computing, STOC 1984 - Washington, United States
Duration: Apr 30 1984May 2 1984

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other16th Annual ACM Symposium on Theory of Computing, STOC 1984
CountryUnited States
CityWashington
Period4/30/845/2/84

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Scaling and related techniques for geometry problems'. Together they form a unique fingerprint.

  • Cite this

    Gabow, H. N., Bentley, J. L., & Tarjan, R. E. (1984). Scaling and related techniques for geometry problems. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984 (pp. 135-143). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800057.808675