This is a demo of half-plane range reporting, the problem of listing all points in the plane that intersect a query half-plane. With a preprocessing step and an efficient data structure an output-sensitive method is possible.

First, an algorithm by Bernard Chazelle (1985) is used to construct the convex layers for n points in the plane in O(nlogn) time. Then, fractional cascading is used to query in O(logn + h) time where h is the output size.

Hit the space bar to walk through the demo.

  Convex layers:
       Chazelle
       Nielsen
       Rufai & Richards

  Additional resources:
       Dynamic Input
       Applications
       Extension to 3D
       Demo source

First, let's add some points to our plane. You can click to the right to add your own points or press P to add random points. In the next step we will be building convex layers from these points.

Hit the space bar when you are ready to continue.

Now that we have our points, we run an O(nlogn) convex layers algorithm. Recall that a single convex hull takes O(nlogn) to compute, so this method is very efficient. Many algorithms that achieve this complexity use a hull-graph data structure which can efficiently maintain the shape of the outer hull even as points are removed.

The most popular of these algorithms was published by Bernard Chazelle (1985), however more recent papers claiming simpler algorithms include Nielsen (1996) and Rufai & Richards (2017).

This produces a list of hulls that can be used to solve our larger problem of determining which points lie to one side of a query line.

We can now visualize these convex layers by listing edges sorted by angle. For each layer determined in the last step you can see the correspondingly colored edge list above.

Try hovering over either elements in the lists or edges in the convex layers to test the mapping. Also recall that the requirement for fractional cascading is a list of sorted lists. That is exactly what we have here. Press space to see how we can use this to our advantage in half-plane range reporting.

With these lists of sorted edges we perform the cascade step of fractional cascading. We promote a constant fraction of each list, so we know by geometric series that the largest list is still linear in it's original size.

We took O(nlogn) to build the convex layers and O(n) to build the fractional cascading table for a total proprocessing step of O(nlogn). Queries in fractional cascading normally take O(logn + k) where k is the number of lists. However, because we return h items our total query time is O(logn + h). We could do as well as O(logn) if we return one element and as poorly as O(n) if we return them all. This is optimal!

You can now perform efficient queries on the combined convex layers/fractional cascading data structure. To determine the points contained in a query half plane draw a line segment with your mouse over the convex layers at the bottom. For each layer we find the point furthest away from the query line until no points in the given layer are in the half plane. (Note: The order of the start and end points determines the direction of the half plane.)

I hope you enjoyed this demo! For any comments or suggestions please contact me through my website.