Problem Description

We are given a plane embedding of a planar connected graph G with n vertices. We wish to store G in some data structure, such that for any query point q in R2 we can quickly determine which face of G (if any) contains q. These queries are called point location queries. We wish to build the data structure once and be able to use it many times for many queries.

History and Solutions

The point location problem is a very common subproblem in computational geometry, and it has been around for a long time. Most of the early optimal results were obtained between 1983 and 1986 (though I did discover some non-optimal solutions from the 1970s). One of the first solutions was Kirkpatrick's triangulation refinement method, discovered in 1983, which is the topic of this project. This solution requires O(n) preprocessing time, O(n) space and can solve queries in O(log n) query time.

Kirkpatrick's triangulation refinement method was one of four different approaches to solving the point location problem using only O(n) space and resulting in O(log n) query time. In 1984, Edelsbrunner et al. developed a point location solution based on segment trees and fractional cascading. This method was named the chain method.

A few years later, in 1986, Sarnak and Tarjan developed a point location solution using persistent search trees. Their claim was that their solution was less complicated than any previous solution.

The fourth approach to solving this problem came in 1988, when Mulmuley developed the randomized incremental algorithm for planar partitioning. This algorithm uses trapezoidal maps and will give O(n) expected size and O(log n) expected query time.

More recent research has been devoted to dynamic point location, where subdivisions can be modified by adding or removing edges in real-time. And according to de Berg et al., point locatoin in higher than two dimensions is still essentially an open problem.

Triangulation Refinement in Detail

In this section I will describe Kirkpatrick's triangulation refinement method for solving point location queries. This is the algorithm that is implemented in a java applet on the Demonstration page. Since a live demonstration is available, I have omitted diagrams from this section. If you wish to see an explanation with static diagrams, the first related link on my Links & References page contains a good description of this algorithm with diagrams. (Alternatively, you can go straight to it here).


Pre-Processing

The nature of this algorithm is triangulation refinement, so the first obvious step is that we must triangulate the given planar graph G. It is assumed that even the outer face is a triangle, which can be achieved by bounding the graph by a large triangle and then re-triangulating.

The second half of the key term for this algorithm is "refinement", so the triangulated graph G must be refined to a smaller graph G'. This is done by choosing an independent set of vertices from G that have a degree that is no more than 8. An independent set of vertices is a set such that no two vertices are neighbours. This set of vertices (and their adjacent edges) are removed from G to get G'.

G' is then re-triangulated and the process continues until only the bounding triangle remains. (For this reason, none of the 3 vertices that make up the bounding triangle may be removed during refinement). This gives us a sequence S1, S2,...,Sh of h triangulations with the following properties:
  1. S1 = G

  2. Sh is the outer triangle of G

  3. h = O(log n)      [recall n is the number of vertices in G]

  4. There is a constant c, 0<c<1, such that for each i, 1<=i<h, the number of vertices of Si+1 is at most c times the number of vertices of Si

  5. For each i, 1<=i<h, and any query point q in R2, if we have located q in Si+1 then we can locate q in Si in O(1) time
(1) and (2) follow from the way the refinement procedure was described. (3) is true, since we remove a constant fraction of the vertices during each refinement phase. This leads us to (4), and why a large independent set of vertices with degree <= 8 must exist? The answer follows from the fact that the graph is a connected planar graph, so it has at most 3n-6 edges. This means that the total sum of all the degrees is at most 6n-12, and jumping ahead a little you can figure out that there are at least 2 + n/2 vertices of degree less than or equal to 8. Property (5) holds because we only remove vertices of small degree. Consider a vertex picked for removal in Si. This vertex has a constant degree d, so once it is removed you are left with a polygon with d edges in Si+1. So if you know that a query point q is in this polygon, then in constant time we can determine which of the d triangles contains q.

During the refinement process, every new triangle that gets created stores a pointer to the triangles that intersect it at the next highest triangulation level. This gives a Directed Acyclic Graph (DAG) where the nodes are the refined triangles, and the topmost node is the bounding outer triangle.

Since a constant fraction of the vertices are removed each time, it is not hard to see that the total space for the triangulations is O(n). This sequence of triangulations, combined with the directed acyclic graph, is the data structure for the triangulation refinement method. For more detailed proofs please refer to the references on my Links & References page.


Querying

Once the sequence of triangulations and the DAG are computed, querying becomes rather simple. You first start with the outer triangle. If the query point q is outside of the outer triangle then it is not contained in any face of G. If q is inside the triangle then you use the DAG to determine which sub-triangle inside the outer triangle contains q. This process is continued until reaching S1 in which case we have determined where q lies in G.

Since there are only O(log n) levels and at each level we only spend O(1) time, the total query time is O(log n).