**Introduction
**

**The Problem and the motivation**

The problem is next: Imagine that you are flying with your airplane and you
have a map of the world in your computer and your GPS tells your position
(latitude/longitude). You want to keep track of the all areas that you cross. Of
course you are lazy and you do not want to do this by hand, so you want to make
your computer to do this for you. But how do you do this? Well your map is
nothing more than a *planar subdivision* and the reading from the GPS is
your position. So we have a set of non-intersecting line segments in a plane and
a point *q *inside one of those areas. The airplane is very fast so also
your search algorithm has to be fast.

**Some history of the point location problem**

As you might already guessed that point location problem has indeed a long
history in computational geometry. Preparata and Shamon presented early results
already in 1985. Four basically different approaches lead to optimal O(log *n*)
search time and O(*n*) storage solutions. Those four were the *chain
method *by Edelsbrunner et al. [1],
which is based on segment trees and *fractional cascading*, the
triangulation *refinement method *by Kirkpatric [2],
the use of *persistency* by Sarnak and Tarjan [3]
and Cole [4], and
the randomized incremental method by Mulmuley [5].

**First Idea**

Naive algorithm would draw vertical lines through all vertices of the subdivision as show in figure 1.1. We store the x-coordinates of the vertices in sorted order in an array. Each slab contains no vertices, so the regions within are nicely ordered from top to bottom.

We take advantage of this fact by storing the segments that each slab intersects in an array

__Algorithm for Point Location__

- Do a binary search by
x-coordinate of *q* against the x-coordinates of the vertices of** S**
to determine which slab

- Do a binary search of

- The label of the edge just below

Figure 1.1 Partition into slabs

**Analysis**

Total running time is O(log *n*):

O(log *n)* - binary search
against O(*n*) vertices of *S*

O(log *n*) - binary search against up to *n* segments intersecting
the slab

What about storage space? For each slab, we need to keep an array long
enough to hold all of the segments intersecting the slab. Storage space
required can be as bad as O(*n*^{2}) figure 1.2.

Figure 1.2. Space required can be as
bad as O(*n*^{2})

Although it may not be quadratic in practice, the textbook [6] suggests typical
storage required would be O(*n*^{3/2}).

Our algorithm seems good because it has good query time but it can take lots
of space. So to improve our algorithm we need to improve our data structure.
The improved data structure is called **the Trapezoidal map***.*