|
 ABSTRACT
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 Rk1 and Rk@@@@ in O(n(lg n)rlg lg n) time and O(n) space, where for Rk@@@@ and k ≥ 3, r &equil; k−2; for Rk1, r &equil; 1, 2, 4 for k &equil; 3, 4, 5 and r &equil; k for k > 5. Other problems solved include Rk1and Rk all nearest neighbors, post office and maximum spanning tree; Rk maxima, Rk rectangle searching problems, and Zkp all nearest neighbors (1 ≤ p ≤ @@@@).
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
|
| |
2
|
B. Chazelle, "Filtering search: a new approach to query-answering," Proc. 24th Annual Symp. on Found. of Comp. Sci., 1983, pp. 122-132.
|
| |
3
|
K.L. Clarkson, "Fast algorithms for the all nearest neighbors problem", Proc. 24th Annual Symp. on Foundations of Comp. Sci., 1983, pp. 226-232.
|
| |
4
|
D. Dobkin and R.J. Lipton, "Multidimensional search problems," SIAM J. Comput. 5, 1976, pp. 181-186.
|
| |
5
|
H. Edelsbrunner and H.A. Maurer, "On the intersection of orthogonal objects," Inf. Proc. Letters, 13, 4, 1981, pp. 177-181.
|
| |
6
|
H. Edelsbrunner and M.H. Overmars, "On the equivalence of some rectangle problems," Inf. Proc. Letters 14, 3, 1982, pp. 124-27.
|
| |
7
|
H. Edelsbrunner and M.H. Overmars, "Batched dynamic solutions to decomposable searching problems," Report F118, Inst. fur Informationsverarbeitung, Tech. Univ. Graz, 1983.
|
| |
8
|
|
| |
9
|
H.N. Gabow, "Scaling algorithms for network problems," Proc. 24th Annual Symp. on Found. of Comp. Sci., 1983. pp. 248-257.
|
| |
10
|
|
| |
11
|
R.L. Graham and P. Hell, "On the history of the minimum spanning tree problem," Ann. History of Computing, to appear.
|
| |
12
|
L.J. Guibas and J. Stolfi, "On computing all north-east nearest neighbors in the L1 metric," Inf. Proc. Letters 17, 1983, pp. 219-223.
|
| |
13
|
|
| |
14
|
|
| |
15
|
|
| |
16
|
|
| |
17
|
D.T. Lee and C.K. Wong, "Voronoi diagrams in L1(L@@@@) metrics with 2-dimensional storage applications," SIAM J. Comput. 9, Feb. 1980, pp. 200-211.
|
| |
18
|
D.T. Lee and C.K. Wong, "Finding intersections of rectangles by range search," J. of Algorithms 2, 1981, pp. 337-347.
|
| |
19
|
|
| |
20
|
P. van Emde Boas, Kaas, R., and Zijlstra, E., "Design and implementation of an efficient priority queue," Math. Systems Theory 10, 1977, pp. 99-127.
|
| |
21
|
P. van Emde Boas, "Preserving order in a forest in less than logarithmic time and linear space," Inf. Proc Letters 6, 3, 1977, pp. 80-82.
|
| |
22
|
|
| |
23
|
|
| |
24
|
A.C. Yao, "On constructing minimum spanning trees in k-dimensional spaces and related problems," SIAM J. Comput. 11, 4, 1982, pp. 721-736.
|
CITED BY 47
|
|
O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States
|
|
|
Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.427-436, May 29-June 01, 1995, Las Vegas, Nevada, United States
|
|
|
|
|
|
Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States
|
|
|
|
|
|
|
|
|
C. Monma , M. Paterson , S. Suri , F. Yao, Computing Euclidean maximum spanning trees, Proceedings of the fourth annual symposium on Computational geometry, p.241-251, June 06-08, 1988, Urbana-Champaign, Illinois, United States
|
|
|
|
|
|
|
|
|
|
|
|
Stephen Alstrup , Cyril Gavoille , Haim Kaplan , Theis Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
|
|
|
A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Keith Frikken , Mikhail Atallah , Marina Bykova, Remote revocation of smart cards in a private DRM system, Proceedings of the 2005 Australasian workshop on Grid computing and e-research, p.169-177, January 01, 2005, Newcastle, New South Wales, Australia
|
|
|
|
|
|
|
|
|
Paolo Ferragina , S. Muthukrishnan , Mark de Berg, Multi-method dispatching: a geometric approach with applications to string matching problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.483-491, May 01-04, 1999, Atlanta, Georgia, United States
|
|
|
Amihood Amir , Gad M. Landau , Usi Vishkin, Efficient pattern matching with scaling, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.344-357, January 22-24, 1990, San Francisco, California, United States
|
|
|
Delis Vasilis , Makris Christos , Sioutas Spiros, A provably efficient computational model for approximate spatiotemporal retrieval, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.40-46, November 02-06, 1999, Kansas City, Missouri, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P. Widmayer , Y. F. Wu , C. K. Wong, Distance problems in computational geometry with fixed orientations, Proceedings of the first annual symposium on Computational geometry, p.186-195, June 05-07, 1985, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2