Range Queries

For both trees we adopt the convention that to the left child of a node has value strictly smaller, and the right child greater than or equal to. See back of document.

(FIG 1): Visited nodes highlighted in yellow. Leafs correspond to points.

(FIG 2): The top level data-structure is on x-coordinate. Nodes we visit in the search are highlighted yellow. If we explore an augmented data-structure, we circle the node with red. The internal data-structures are represented as BST arrays. The nodes of the internal data-structure have been highlighted if they are visited during the search.

Line of Maximum Points

This problem reduces to finding the point in the dual that has the maximum number of intersecting lines. We first form the arrangement of our dual-graph (\(O(n^2)\)). Assuming our arrangement is stored as a graph, we simply traverse the graph (\(O(n^2)\)) and find the node of maximum degree. Node of maximum degree \(\implies\) vertex of maximum intersections \(\implies\) line with most points on it \(\square\).

Points Above a Line

We form the dual problem, which is to count the number of lines below a query point. We form the arrangement of this graph, and label each face with the number of lines that lie strictly below it. Once this is done we simply use a point-query (trapezoidal decomp) to find the face that any query point belongs to, and report the stored value.

Forming the Dual

\(s\in S\) lies above \(l\) IFF \(s*\) lies below \(l*\) (Property 3 in slides). The dual-problem then is to find the number of lines \(\in S*\) that lie below our query point \(l*\).


We form the arrangement \(A(S^*)\) in \(O(n^2)\) time. We mark faces \(\in A(S^*)\) with the number of lines \(\in S*\) lying strictly below it (RTP: correctness and \(O(n^2)\) time. This forms a planar-subdivision with \(O(n^2)\) edges.

Our query then reduces to finding the face \(l^*\) resides in. To do this we construct the trapezoidal-decomposition data-structure on \(A(S^*)\). This gives us a total:

  • Preprocessing time: expected \(O(n^2 log n)\)
  • Space: expected \(O(n^2)\)
  • Query-time: \(O(\log n)\)

Where we have made use of the fact that \(O(\log(n^2)) = O(\log n)\).

Dual point resides in face with x lines below it \(\implies\) Original line has x points above it \(\square\). All that remains is to prove the face-annotation procedure.

Face Annotation

We want to annotate every face with the number of edges lying below it in \(O(n^2)\) total time. We do so by first labeling the edges of this arrangement with this information. We do so iteratively. We find all the edges which tend to negative infinity (we can be lazy -- simply iterating over ever edge in \(O(n^2)\).

We can then sort these edges by slope. There can be one edge going to negative infinity for every line in the original graph, so this is \(O(n\log n)\). From here, the edge with highest negative slope will be above all others, the line with second highest negative slope will be above all but the first and so on. We annotate the edges using this order (FIG 3).

Initial Steps