TY - GEN

T1 - Scaling and related techniques for geometry problems

AU - Gabow, Harold N.

AU - Bentley, Jon Louis

AU - Tarjan, Robert E.

N1 - Funding Information:
Seal/rig has been applied to network problems (Edmonds and Karp, 1972; Gabow, 1983). Consider a problem defined on nonnegative integers; in geometry these are the point coordinates. Let N be the largest integer and I = Jig N\]+I. View each number as its l bit ~:binary expansion b t : ' " b~. The method works by consid-=:ering l+l scales s. s = 0,I ..... l, where scale s takes the numbers to be b I .. • b.. This paper applies scaling in two ways. The first is to view the solution to the scale s-1 problem as an approximation to the scale s prob-lem. The solution is refined over l + 1 scales until it is correct. This is similar to network scaling and gives an efficient all nearest neighbors algorithm. The second x This research was supvorted in paa:t by the NationalS cience Foundation under Grant IdeS-8 302648 and in part by BellL aboretccies.
Publisher Copyright:
© 1984 ACM.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

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 -