article

Optimal Partition Trees

Author:

Timothy M. ChanAuthors Info & Claims

Discrete & Computational Geometry, Volume 47, Issue 4

Pages 661 - 690

Published: 01 June 2012 Publication History

Abstract

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157---182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n1ź1/d) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n1+ź) preprocessing time for any fixed ź>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315---334, 1992) requires O(nlogn) preprocessing time but O(n1ź1/dlogO(1)n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n1ź1/d) query time with high probability. Our method has several advantages: It is conceptually simpler than Matoušek's O(n1ź1/d)-time method. Our partition trees satisfy many ideal properties (e.g., constant degree, optimal crossing number at almost all layers, and disjointness of the children's cells at each node).It leads to more efficient multilevel partition trees, which are needed in many data structuring applications (each level adds at most one logarithmic factor to the space and query bounds, better than in all previous methods).A similar improvement applies to a shallow version of partition trees, yielding O(nlogn) time, O(n) space, and O(n1ź1/źd/2ź) query time for halfspace range emptiness in even dimensions dź4. Numerous consequences follow (e.g., improved results for computing spanning trees with low crossing number, ray shooting among line segments, intersection searching, exact nearest neighbor search, linear programming queries, finding extreme points, ź).

References

[1]

Afshani, P., Chan, T.M.: Optimal halfspace range reporting in three dimensions. In: Proc. 20th ACM-SIAM Sympos. Discrete Algorithms, pp. 180---186 (2009)

Digital Library

[2]

Agarwal, P.K.: Intersection and Decomposition Algorithms for Planar Arrangements. Cambridge University Press, Cambridge (1991)

[3]

Agarwal, P.K.: Ray shooting and other applications of spanning trees with low stabbing number. SIAM J. Comput. 21, 540---570 (1992)

Digital Library

[4]

Agarwal, P.K.: Range searching. In: Goodman, J., O'Rourke, J. (eds.) CRC Handbook of Discrete and Computational Geometry. CRC Press, New York (2004)

[5]

Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Discrete and Computational Geometry: Ten Years Later, pp. 1---56. AMS, Providence (1999)

[6]

Agarwal, P.K., Matoušek, J.: On range searching with semialgebraic sets. Discrete Comput. Geom. 11, 393---418 (1994)

Digital Library

[7]

Agarwal, P.K., Sharir, M.: Applications of a new space-partitioning technique. Discrete Comput. Geom. 9, 11---38 (1993)

Digital Library

[8]

Agarwal, P.K., Aronov, B., Suri, S.: Stabbing triangulations by lines in 3D. In: Proc. 10th ACM Sympos. Comput. Geom., pp. 267---276 (1995)

Digital Library

[9]

Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput. 29, 912---953 (1999)

Digital Library

[10]

Agarwal, P.K., Arge, L., Erickson, J., Franciosa, P.G., Vitter, J.S.: Efficient searching with linear constraints. J. Comput. Syst. Sci. 61, 194---216 (2000)

Digital Library

[11]

Amato, N.M., Goodrich, M.T., Ramos, E.A.: Parallel algorithms for higher-dimensional convex hulls. In: Proc. 35th IEEE Sympos. Found. Comput. Sci., pp. 683---694 (1994)

Digital Library

[12]

Arora, S., Hazan, E., Kale, S.: Multiplicative weights method: a meta-algorithm and its applications. Theory Comput. (2012, to appear)

[13]

Arya, S., Mount, D.M., Xia, J.: Tight lower bounds for halfspace range searching. In: Proc. 26th ACM Sympos. Comput. Geom., pp. 29---37 (2010)

Digital Library

[14]

Bentley, J., Saxe, J.: Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1, 301---358 (1980)

[15]

Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14, 463---479 (1995)

Digital Library

[16]

Chan, T.M.: Fixed-dimensional linear programming queries made easy. In: Proc. 12th ACM Sympos. Comput. Geom., pp. 284---290 (1996)

Digital Library

[17]

Chan, T.M.: Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom. 16, 369---387 (1996)

Digital Library

[18]

Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pp. 423---429 (2004)

[19]

Chan, T.M., Snoeyink, J., Yap, C.-K.: Primal dividing and dual pruning: output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams. Discrete Comput. Geom. 18, 433---454 (1997)

[20]

Chazelle, B.: Lower bounds on the complexity of polytope range searching. J. Am. Math. Soc. 2, 637---666 (1989)

[21]

Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9, 145---158 (1993)

Digital Library

[22]

Chazelle, B: Cuttings. In: Mehta, D.P., Sahni, S. (eds.) Handbook of Data Structures and Applications, pp. 25.1---25.10. CRC Press, Boca Raton (2005)

[23]

Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10, 229---249 (1990)

[24]

Chazelle, B., Rosenberg, B.: Simplex range reporting on a pointer machine. Comput. Geom., Theory Appl. 5, 237---247 (1996)

Digital Library

[25]

Chazelle, B., Welzl, E.: Quasi-optimal range searching in space of finite VC-dimension. Discrete Comput. Geom. 4, 467---489 (1989)

Digital Library

[26]

Chazelle, B., Sharir, M., Welzl, E.: Quasi-optimal upper bounds for simplex range searching and new zone theorems. Algorithmica 8, 407---429 (1992)

Digital Library

[27]

Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM J. Comput. 17, 830---847 (1988)

Digital Library

[28]

Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42, 488---499 (1995)

Digital Library

[29]

Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387---421 (1989)

Digital Library

[30]

de Berg, M., Schwarzkopf, O.: Cuttings and applications. Int. J. Comput. Geom. Appl. 5, 343---355 (1995)

[31]

Dobkin, D., Edelsbrunner, H.: Organizing point sets in two and three dimensions. Report f130, Inst. Informationsverarb., Tech. Univ. Graz, Austria (1984)

[32]

Edelsbrunner, H., Huber, F.: Dissecting sets of points in two and three dimensions. Report f138, Inst. Informationsverarb., Tech. Univ. Graz, Austria (1984)

[33]

Edelsbrunner, H., Welzl, E.: Halfplanar range search in linear space and O(n0.695) query time. Inf. Process. Lett. 23, 289---293 (1986)

Digital Library

[34]

Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., Welzl, E.: Implicitly representing arrangements of lines or segments. Discrete Comput. Geom. 4, 433---466 (1989)

Digital Library

[35]

Haussler, D., Welzl, E.: Epsilon-nets simplex range queries. Discrete Comput. Geom. 2, 127---151 (1987)

Digital Library

[36]

Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: shoot a ray, take a walk. J. Algorithms 18, 403---431 (1995)

Digital Library

[37]

Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13---30 (1963)

[38]

Matoušek, J.: Spanning trees with low crossing number. RAIRO Theor. Inform. Appl. 25, 103---124 (1991)

[39]

Matoušek, J.: Efficient partition trees. Discrete Comput. Geom. 8, 315---334 (1992)

Digital Library

[40]

Matoušek, J.: Reporting points in halfspaces. Comput. Geom., Theory Appl. 2, 169---186 (1992)

Digital Library

[41]

Matoušek, J.: Linear optimization queries. J. Algorithms 14, 432---448 (1993). Also with O. Schwarzkopf in Proc. 8th ACM Sympos. Comput. Geom., pp. 16---25, 1992

Digital Library

[42]

Matoušek, J.: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10, 157---182 (1993)

Digital Library

[43]

Matoušek, J.: Geometric range searching. ACM Comput. Surv. 26, 421---461 (1994)

Digital Library

[44]

Matoušek, J.: Lectures on Discrete Geometry. Springer, Berlin (2002)

[45]

Matoušek, J., Schwarzkopf, O.: On ray shooting in convex polytopes. Discrete Comput. Geom. 10, 215---232 (1993)

Digital Library

[46]

Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)

[47]

Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs (1994)

[48]

Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)

[49]

Ramos, E.: On range reporting, ray shooting, and k-level construction. In: Proc. 15th ACM Sympos. Comput. Geom., pp. 390---399 (1999)

Digital Library

[50]

Ramos, E.: Linear programming queries revisited. In: Proc. 16th ACM Sympos. Comput. Geom., pp. 176---181 (2000)

Digital Library

[51]

Seidel, R.: Constructing higher-dimensional convex hulls at logarithmic cost per face. In: Proc. 18th ACM Sympos. Theory Comput, pp. 404---413 (1986)

Digital Library

[52]

Welzl, E.: On spanning trees with low crossing numbers. In: Monien, B., Ottmann, T. (eds.) Data Structures and Efficient Algorithms. Lect. Notes Comput. Sci., vol. 594, pp. 233---249. Springer, Berlin (1992)

[53]

Willard, D.E.: Polygon retrieval. SIAM J. Comput. 11, 149---165 (1982)

[54]

Yao, A.C., Yao, F.F.: A general approach to D-dimensional geometric queries. In: Proc. 17th ACM Sympos. Theory Comput., pp. 163---168 (1985)

[55]

Yao, F.F.: A 3-space partition and its applications. In: Proc. 15th ACM Sympos. Theory Comput., pp. 258---263 (1983)

[56]

Yao, F.F., Dobkin, D.P., Edelsbrunner, H., Paterson, M.S.: Partitioning space for range queries. SIAM J. Comput. 18, 371---384 (1989)

Digital Library

Cited By

Agarwal PHu XSintos SYang J(2024)On Reporting Durable Patterns in Temporal Proximity GraphsProceedings of the ACM on Management of Data10.1145/36511442:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651144
Alman JLiang JSong ZZhang RZhuo DOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Bypass exponential time preprocessingProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668209(48110-48137)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668209
Lu STao YGeerts FNgo HSintos S(2023)Indexing for Keyword Search with Structured ConstraintsProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588663(263-275)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588663
Show More Cited By

Optimal Partition Trees
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Optimal partition trees
SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Back in SoCG'92, Matousek gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n^1-1/d) ...
Efficient partition trees

We prove a theorem on partitioning point sets inEd (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n1 1/d(...
Orthogonal range searching on the RAM, revisited
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: We present two data structures for 2-d orthogonal range ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete & Computational Geometry

Discrete & Computational Geometry Volume 47, Issue 4

June 2012

114 pages

ISSN:0179-5376

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer Science+Business Media, LLC.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agarwal PHu XSintos SYang J(2024)On Reporting Durable Patterns in Temporal Proximity GraphsProceedings of the ACM on Management of Data10.1145/36511442:2(1-26)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651144
Alman JLiang JSong ZZhang RZhuo DOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Bypass exponential time preprocessingProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668209(48110-48137)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668209
Lu STao YGeerts FNgo HSintos S(2023)Indexing for Keyword Search with Structured ConstraintsProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588663(263-275)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588663
Afshani PCheng P(2023)Lower Bounds for Semialgebraic Range Searching and Stabbing ProblemsJournal of the ACM10.1145/357857470:2(1-26)Online publication date: 18-Apr-2023
https://dl.acm.org/doi/10.1145/3578574
Rubin N(2022)An Improved Bound for Weak Epsilon-nets in the PlaneJournal of the ACM10.1145/355598569:5(1-35)Online publication date: 27-Oct-2022
https://dl.acm.org/doi/10.1145/3555985
Song ZYang SZhang RRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Does preprocessing help training over-parameterized neural networks?Proceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3542014(22890-22904)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3542014
Hu XYi KTao Y(2019)Output-Optimal Massively Parallel Algorithms for Similarity JoinsACM Transactions on Database Systems10.1145/331196744:2(1-36)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3311967
Hu XTao YYang YZhou S(2018)Semi-Group Range Sum RevisitedAlgorithmica10.1007/s00453-017-0307-380:4(1315-1329)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s00453-017-0307-3
Afshani PBarbay JChan T(2017)Instance-Optimal Geometric AlgorithmsJournal of the ACM10.1145/304667364:1(1-38)Online publication date: 17-Mar-2017
https://dl.acm.org/doi/10.1145/3046673
Hu XTao YYi KSallinger EVan den Bussche JGeerts F(2017)Output-optimal Parallel Algorithms for Similarity JoinsProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3056110(79-90)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3056110
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents