Scaling and Related Techniques for Geometry Problems

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

Authors

• Harold N. Gabow
• Jon Louis Bentley
• Robert Endre Tarjan

Keywords

No keywords are indexed for this paper.