TY - GEN
T1 - Scaling and related techniques for geometry problems
AU - Gabow, Harold N.
AU - Bentley, Jon Louis
AU - Tarjan, Robert E.
N1 - Publisher Copyright:
© 1984 ACM.
PY - 1984/12/1
Y1 - 1984/12/1
N2 - 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≤∞).
AB - 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≤∞).
UR - http://www.scopus.com/inward/record.url?scp=85020601782&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85020601782&partnerID=8YFLogxK
U2 - 10.1145/800057.808675
DO - 10.1145/800057.808675
M3 - Conference contribution
AN - SCOPUS:85020601782
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 135
EP - 143
BT - Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984
PB - Association for Computing Machinery
T2 - 16th Annual ACM Symposium on Theory of Computing, STOC 1984
Y2 - 30 April 1984 through 2 May 1984
ER -