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 &equil; k?2; for R k 1 , r &equil; 1, 2, 4 for k &equil; 3, 4, 5 and r &equil; 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 ? @@@@).
scale geometry computational geometry update data structures minimum spanning tree timing space nearest neighbor