Planar Point Location
- The Planar Point Location algorithm is used to efficiently determine in which Voronoi cell, a new
vertex of the refined Q-triangulation will be mapped to
- It consists of subdividing the Voronoi Diagram into several slabs,
such that the Voronoi edges inside each slab are lexicographically
ordered
- Given a point in the complex plane, we first use its x-coord to
determine in which slab the point lies, and then we use its y-coord to
determine what Voronoi edges are above and below the point. With that
information, we can easily pin point what Voronoi cell contains the
point
