Halfplanar range search in linear space and \(O(n^{0.695})\) query time (Q1097038)

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.