Halfplanar range search in linear space and \(O(n^{0.695})\) query time. (English) Zbl 0634.68064

Let S denote a set of n points in the Euclidean plane. A halfplanar range query asks for the number of points in S which are contained in a given halfplane h. The authors introduce a data structure which stores S in O(n) space allowing an \(O(n^{\log_ 2(1+\sqrt{5})-1})\) query-time implementation of the above problem. The structure which they call conjugation tree, but in more recent work is often referred to as ham- sandwich tree, can be built in O(n log n) time. This tree structure can be seen as an improvement of Willard’s polygon tree.
A line \(\ell\) is a bisector of S if it partitions S into two sets P and Q which both contain at most n/2 points. Line \(\ell\) is called a ham- sandwich cut of two sets P and Q if it bisects both of them. Such a cut always exists and the ham-sandwich tree T(S,\(\ell)\) can now be roughly defined as follows. The root stores \(\ell\) and the points in \(S\cap \ell\). Its two sons are the trees \(T(P,\ell_ 1)\) and \(T(Q,\ell_ 1)\), where \(\ell_ 1\) is the ham-sandwich cut of sets P and Q, the partition of S by \(\ell\). In splitting set S in four approximately equal parts within one “level”, the ham-sandwich tree is, in a way, related to the well-known quad tree, although now, the separating lines are no longer necessarily axis-parallel.
After the definition of the tree structure, the authors state their algorithm for the halfplanar range query and give the \(O(n^{0.695})\) worst-case time analysis. Then they shortly address how results of Megiddo can be used to construct the tree in O(n log n) time. They end their paper by noting that ham-sandwich trees may be made dynamic using generic methods of Overmars and van Leeuwen.
Reviewer: E.P.Mücke


68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
52A37 Other problems of combinatorial convexity
Full Text: DOI


[1] Bentley, J. L., Multidimensional binary search trees used for associative searching, Comm. ACM, 18, 509-515 (1975) · Zbl 0306.68061
[2] Chazelle, B.; Guibas, L.; Lee, D. T., The power of geometric duality, (Proc. 24th Symp. on Foundations of Computer Science (1983)), 217-225
[3] Edelsbrunner, H.; Kirkpatrick, D. G.; Maurer, H. A., Polygonal intersection searching, Inform. Process. Lett., 14, 74-79 (1982) · Zbl 0486.68051
[4] Edelsbrunner, H.; Welzl, E., Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput., 15, 271-284 (1986) · Zbl 0613.68043
[5] Finkel, R. E.; Bentley, J. L., Quad trees—a data structure for retrieval on composite keys, Acta Informatica, 4, 1-9 (1974) · Zbl 0278.68030
[6] Fredman, M. L., The inherent complexity of dynamic data structures which accomodate range queries, (Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science (1980)), 191-199
[7] Knuth, D. E., Fundamental Algorithms: The Art of Computer Programming I (1973), Addison-Wesley: Addison-Wesley Reading, MA, Chap. 1 · Zbl 0191.17903
[8] Knuth, D. E., Sorting and Searching: The Art of Computer Programming III (1973), Addison-Wesley: Addison-Wesley Reading, MA, Chap. 6 · Zbl 0302.68010
[9] N. Megiddo, Partitioning with two lines in the plane, J. Algorithms, to appear.; N. Megiddo, Partitioning with two lines in the plane, J. Algorithms, to appear. · Zbl 0582.51013
[10] Overmars, M. H.; van Leeuwen, J., Worst-case optimal insertion and deletion methods for decomposable searching problems, Inform. Process. Lett., 12, 168-173 (1982) · Zbl 0459.68026
[11] Samet, H., Neighbor finding techniques for images represented by quadtrees, Comput. Graphics and Image Process., 18, 37-57 (1982) · Zbl 0531.68041
[12] Willard, D. E., Polygon retrieval, SIAM J. Comput., 11, 149-165 (1982) · Zbl 0478.68060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.