\input CS445Hdr
% This is CS445N5.tex of February 18, 10:27 AM
\def\header{5. Point location problems}
\def\title{Lectures 9--10}

\chap{\header.}

\sect{5.1 Overview.}

In this chapter we will examine the so-called {\it point location problem}:
given a partition of the plane in two or more regions
$F1̌, F2̌, \ldotss, Fm̌$, and one or more points
$p1̌, p2̌, \ldotss, pǩ$,
find out which points are in which region. A special case
is when we have a single point $p$ and just two regions, a figure $F$ and
its complement; we have then the {\it point inclusion problem},
namely to decide if $p$ is in $F$ or not.\par

This problem is also related to that of finding the intersection of two
or more figures, and to that of decomposing a given figure
into parts with specific properties (like convex or triangular). Both these
problems will be studied in the next few chapters.\par

The point inclusion problem has lots of practical applications. For example,
in interactive computer graphics it is often necessary to determine
which of the objects on the screen the user is pointing to,
given the current coordinates of the pointing
device (mouse, light pen, etc.).\par

Another application is in the statistical technique known as {\it cluster
analysis}. For example, a statistician might want to develop a model
to predict the sex of a person based on a set of numerical measurements,
say weight and height. To develop such a model, he measures a sample
of men and women and plots the data as two sets of points
on the height-weight plane. If there is any merit to the idea, it should
be possible to partition the plane in two
(reasonably simple) regions: $F$, containing
most of the female subjects, and $M$, containing most of the male ones.\fig4
This phase constitutes cluster analysis proper; once
such regions have been found,
the sex of a new subject can be predicted to be female or male
depending on whether the corresponding point falls in $F$ or in $M$.
The abstract point inclusion problem not only has an obvious connection
with this prediction phase, but frequently occurs as a subproblem also in
the initial cluster analysis.\par

A third application of point location algorithms is the
{\it range-query problem} in database management, where
we want to locate all entries in a file for which certain attributes
fall in specified ranges.
In geometrical terms, we can wiew each entry in the file as a point in
a $k$-dimensional space (whose coordinates are its numerical
attributes) and then the query reduces to the determination of
all points which fall inside a given box.\par

In most applications, point-location problems have to be solved in a
``partially on-line’’ fashion: the points are given one by one in
an unpredictable sequence and each has to be located, against
a fixed set of regions, before the next point is given. Sometimes,
as in the range-query problem, the situation is reversed:
the set of points is known beforehand, and the regions are
given one by one and are to be processed on-line.\par

This has to be kept in mind when comparing the performance of
point-location algorithms. Most of those algorithms assume
that the regions (or the points, in the range-query case) are represented in
some specific data structure, especially designed to
increase the efficiency of the queries.
Therefore, besides the cost of each query, we must consider also the
time and space consumed in
building such representation. If the application is such that
the regions can be occasionaly modified, we must consider also the cost
of updating such representation.

We will not study the range-query problem in this chapter, since it
will occur naturally in the study of intersection problems (chapter 6).
In what follows, we will be concerned
exclusively with the problem of locating one of a sequence of input
points against a fixed ``data base’’, a set of regions.\par

\sect{5.2. Convex and star-shaped polygons.}

One of the simplest instances of this problem
is the determination of whether a point $p$ is inside
a convex polygon $H$. We already solved this problem in section 4.4:
if we know an interior point $o$ of $H$, and its vertices
$\langle v1̌, v2̌, \ldotss, vň\rangle$ are kept
sorted in in order of increasing polar angle as seen from $o$,
then by binary search we can locate the
angle $vǐov{̌i+1}$ that contains $p$.\fig4
It is then a trivial
matter to check whether the line $vǐv{̌i+1}$ separates $p$ and
$o$, and this tells us whether $p$ is inside $H$ or not.\par

This algorithm has query time of $O(\log n)$, and requires
$O(n)$ storage for the vertices $vǐ$. Preprocessing time
is $O(n\log n)$ if the vertices are given in random order, which is rarely the
case; in most cases, they will be given in counterclockwise order,
so preprocessing involves only storing the points in an array
and possibly precomputing the polar angles of the $vǐ$ (see
section 4.2). Of course, this requires at most $O(n)$ time.\par

$H$ need not be convex for this method to work; all we need
is that for some interior point $o$, the angle $vǐv{̌i+1}$ between
any two successive vertices contain no other vertex of $H$; such
polygons are known as {\it star-shaped}. In general, we can
say that a figure is star-shaped if there exists an interior
point $o$ that can ``see’’ the whole boundary of the figure, i.e.
such that any ray from $o$ meets the boundary at a single point.\fig4
Star-shaped figures have many interesting properties that are
somewhat reminiscent of those of convex ones. Of course, not all
figures are star-shaped, and not all interior points of a star-shaped figure
can serve as the origin $o$ in the definition above.\par

Given an arbitrary
figure $F$, we define the {\it kernel} of $F$ as the set of all it interior
points for which it is star-shaped, i.e. which can see its entire boundary
in the above sense. The two following facts hold:\par

\theorem{5.1}{The interior of a figure $F$ coincides with
its kernel iff $F$ is convex}
\proof{If the figure were not convex, there would be a line
$\lscr$ passing through an interior point $p$ and meeting
the boundary of $F$ at three or more points (theorem 3.10).
Then one of the rays of $\lscr$ with origin $p$ would
contain two or more points of the boundary, so $p$
would not be in the kernel of $F$.}

\theorem{5.2}{The kernel of a simple polygon
$F=\langle v1̌, v2̌, \ldotss, vň\rangle$ is a convex polygon.}
\proof{All the points that can
``see’’ an abitrary edge $vǐv{̌i+1}$ are those in
the (open) left half-plane defined by the
line through $vǐ$ and $v{̌i+1}$. Therefore, the kernel of $F$ is the
intersection of all such half-planes; since they are convex
sets, the kernel too is convex.}

Actually, the following fact (whose proof is left to the reader) is also true:\par

\theorem{5.3}{The kernel of an arbitrary figure $F$ is a convex set.}

\digress{Note that the definition of star-shapedness given above does
not include degenerate cases like these:\fig3
This policy implies that the kernel of a figure is an open set
(i.e., does not include its boundary points).}

\sect{5.3. Monotone polygons.}

Instead of ordering the vertices cyclically by their polar angles,
as suggested above, we can use the half-hull techniques of section 4.10:
the convex polygon $H$ is represented as two polygonal chains,
the ``upper half’’ $H↑U$ and the ``lower half’’ $H↑L$,
whose vertices are linearly sorted by their $x$-coordinates.
By binary search, we can locate two consecutive vertices
$vǐ, v{̌i+1}$ on the lower half such that
$x{̌vǐ}\leq xp̌ \leq x{̌v{̌i+1}}$; then $p$ will be
above $H↑L$ iff it is above the line $vǐv{̌i+1}$. A similar
test decides whether $p$ is below $H↑U$. This gives an
$O(\log n)$ time test for point inclusion in $H$.\par

It can be seen that this method can be applied
to a non-convex polygon, as long as its boundary
can be decomposed into two polygonal chains in such a way that
the the vertices along each chain have monotonically
increasing or decreasing $x$-coordinates. Of course,
the idea still works if the $x$-axis is replaced by
some other suitable direction $d$.\par

Such chains and polygons are said to be {\it monotone} along the direction
$d$. The intersection of a monotone polygon $H$ with any line
perpendicular to $d$ is either empty or a single segment;
this property can be used to define monotone figures in general.
As we can see, monotonicity is a property quite similar to
star-shapedness in many respects; in fact,
a monotone chain can be considered to be a segment
of a star-shaped polygon as seen from a point $o$ at infinity.\par

Again, not all polygons are monotone (counterexamples require
at least six edges), and many are monotone only for
a proper subset of all possible directions. The reader may wish
to prove the following properties:\par

\theorem{5.4}{A figure $F$ is convex iff it is monotone with
respect to all directions $d$ on the plane.}

\theorem{5.5}{The set of directions along which a non-convex polygon
is monotone defines a pair of diametrically opposite and equal arcs
on the direction circle.}

\digress{Those who took the Computer Graphics course last year
will probably remember that we can check whether a simple polygon
is monotone (and find a suitable direction $d$) in time linear with
the number of its vertices.\par
\dp The definition of monotonicity can be
generalized to allow for polygons whose boundary can be decomposed into
$2t$ monotone chains w.r.t. some direction $d$; the figure below
shows a ``threefold monotone’’ polygon.\fig3
Point inclusion in such polygons can be tested in $O(t\log n)$ time
by a trivial extension of the standard algorithm. A similar result
would be true for ``$t$-fold star-shaped’’ polygons, which
can be defined in an analogous way. Unfortunately,
some simple polygons (e.g, a star with ${n\over 2}$ points)
are $t$-fold monotone only for $t=\Omega(n)$, so this
idea is not as useful as it may seem at first glance.}

\sect{5.4 Inclusion in a simple polygon.}

Next in order of increasing complexity is the problem
of point inclusion in an arbitrary simple polygon $H$. One
can readily think of several algorithms that do not
require any special processing.\par

The {\it winding number} of a curve $L$ with respect to
a point $p$ not in it can be loosely defined as the number of
complete 360\deg turns that a point $q$ describes around $p$ while
scanning $L$ in a consistent direction.
If $L$ is a simple closed curve, the winding number is either
$0$ or $\pm1$ depending on whether $p$ is outside or inside it
(in the second case, the sign is $+$ iff $L$ is scanned
counterclockwise).\par

When the curve is a polygon
$H=\langle v1̌, v2̌, \ldotss, vň\rangle$, the winding
number is given by the expression
$${1\over{2\pi}}\sum{̌1\leq i\leq n}\angle vǐov{̌i+1}\eqno(1)$$
where each term is measured in the range $(-\pi, \pi)$ and, as
usual, the indices ``wrap around’’ cyclically. This formula
gives an algorithm with $O(n)$ query time and $O(n)$ required
space.\par

Note that the angles in formula (1) must be computed
with enough accuracy to give a total absolute error of less than $\pi$,
otherwise the winding number will be ambiguous. This precludes
the use of numerically simple approximations, like the
cross products and square arcs discussed in section 4.2.1.\par

Another method is based on the following well-known topological
property of closed lines:\par

\theorem{5.6 {\rm (Jordan)}}{A point $p$ is inside a simple
closed line $L$ iff a ray with origin $p$ crosses $L$ an odd
number of points.}

Therefore, we can test whether $p$ is inside in a simple polygon
$H=\langle v1̌, v2̌, \ldotss, vň\rangle$ by counting how many edges
$vǐv{̌i+1}$ intersect the horizontal ray to the left of $p$.
This method also requires $O(n)$ space and $O(n)$ query time,
but the computation for each edge is considerably faster
than in the winding number method.

\digress{The main problem with this algorithm is the handling of
degeneracies: edges that just touch the test ray, or that lie on
it As is illustrated in the examples below, such intersections
may or may not correspond to legitimate ``crossings’’
in the sense assumed by theorem 5.6.\fig4\par

\dp Such cases can be handled in a straightforward way, by examining
enough adjacent edges to determine whether the intersection
is a ``crossing’’ or a ``tangency point’’, i.e. whether it should or
not be counted. This technique makes for rather messy code, and
one wonders whether some simpler trick will also get the count straight.
We might think the problem arises because an intersection at
vertex $vǐ$ is counted twice (once for each adjacent edge),
so the solution would be to assume that each edge $vǐv{̌i+1}$
includes $vǐ$ but not $v{̌i+1}$.
Unfortunately, this is not true, as the examples above show;
however, if we assume each edge includes
only its {\it highest} endpoint (and if we ignore horizontal edges
altogether), the parity of the intersection count comes out miraculously
correct! The only extra precaution we must take is to check
whether $p$ is on some edge or coincides with a vertex, in which
case $p$ is neither inside nor outside $H$.

\dp We should also remark that both tests can be used to extend
the definition of ``inside’’ and ``outside’’ to self-intersecting,
connected curves. In this case, the winding number $w$ can assume
other integer values besides 0 and $\pm1$. We can take either $w=0$
or $w\modop 2=0$ to mean ``outside’’; the former choice may seem
somewhat more natural, but only the second can be expressed
in a form analogous to theorem 5.6.}

If we are prepared to pay for extra storage and for some preprocessing,
we can significantly reduce the query time. One way to do this is to
decompose the plane into vertical strips by drawing $n$ vertical lines
$\lscr1̌, \lscr2̌, \ldotss, \lscrň$ passing through the vertices of the
polygon and sorted in order of increasing $x$-coordinate.\fig4\par

The plane strip between successive
lines $\lscrǐ$ and $\lscr{̌i+1}$ contains no vertices of $H$, and
therefore its intersection with $H$ is a set of trapezoids whose
bases (eventually degenerate) are on $\lscrǐ$ and $\lscr{̌i+1}$,
and whose sides $e{̌i1}, e{̌i2}, \ldotss $ are on the edges
of $H$ that intercept the strip. Since $H$ is simple, the $e{̌ij}$s
do not intersect, and they can be linearly ordered
from top to bottom in each strip.\par

Given a table with all $e{̌ij}$, sorted as described
above, we can easily check whether $p$ is inside
or outside $H$:\par

\algorithm{5.1}{Point inclusion in a simple polygon by decomposition into
vertical strips.}{
\step 1. [Find strip.] {By a binary search on $i$, find two consecutive
lines $\lscrǐ$ and $\lscr{̌i+1}$ that bracket point $p$. If $p$ is to the
left of $\lscr1̌$ or to the right of $\lscrň$, stop ($p$ is outside $H$).}
\step 2. [Find trapezoid.] {Do a binary search on $j$ to find
in the strip between $\lscrǐ$ and $\lscr{̌i+1}$ two
consecutive edges $e{̌ij}$ above $p$ and $e{̌i,j+1}$ below $p$. If
$p$ is above $e{̌i1}$, or below the last $e{̌ij}$ in strip $i$,
stop ($p$ is outside $H$).}
\step 3. [Check side.] {If $j$ is odd, report that $p$ is inside $H$,
otherwise report it is outside.}}

This algorithm provides a very good query time, namely $O(\log n)$
(since we have $n$ strips, and each can intercept at most $n$ edges).
The storage and preprocessing costs are rather prohibitive:
the size of the table is $\Omega(n↑2)$ in the worst case, and its
construction requires $\Omega(n↑2)$ time. The example
below illustrates the kind of polygons which realize this worst case.
\fig4\par

\digress{Incidentally, in the case when $H$ is monotone
with respect to the $x$-axis, there will be only
one trapezoid per strip. Algorithm 5.1 then becomes an
alternative formulation of that dicussed in the preceding section,
based on checking $p$ separately against the upper and the lower
boundaries of $H$.
The two algorithms are quite similar, both in their concept and
in their asymptotic costs, even though the trapezoid version requires
twice as much space as the other. We may also remark that, when $H$
is monotonic, the table of trapezoid edges has at most $2n-2$ entries,
and can be built in linear time.}

\sect{5.4. Planar subdivisions and Euler’s relation.}

Algorithm 5.1 is based on the decomposition of
the given polygon and the region around it into small pieces
(trapezoids in this case) and the determination of the piece that
contains the given point. In other words, we reduced the point
inclusion problem for a general polygon to the point location
problem for a collection of regions with restricted shape.\par

Let’s therefore examine the point location problem in more general terms.
By a {\it planar subdivision} we mean a partition
of the plane into $nf̌$ regions (faces) with disjoint interiors,
defined by $nv̌$ distinct points (vertices) and a total of
$ně$ nonintersecting lines (edges), with each
edge incident to two vertices, each face bounded by
one or more edges, and each vertex incident to
at least two edges.\fig4
One or more of the faces will be necessarily infinite, and
one of the vertices may be located at infinity. If there are no
such infinite vertices, the subdivision will be said to be {\it bounded};
a bounded subdivision has a single infinite region, called the {\it background}
or {\it exterior face}.
\par

It is easy to see that $nv̌\leq ně$ and
$nf̌\leq ně+1$. Therefore, the total number of edges $ně$
is a good measure of the complexity of the subdivision.
This number will be denoted by $n$ in the analysis of
point location algorithms.\par

We will be concerned only with {\it straight-line subdivisions}
of the plane, i.e. subdivisions where all edges are straight.
To simplify later results, we will also require that all edges be
either rays or segments (i.e., no doubly infinite lines), and that
no two rays have the same origin. A straight-line subdivision is
said to be {\it convex} if all faces are convex\foot1{Note
that a subdivision with convex faces cannot have curved edges.}, and
{\it monotone} if all faces are monotone polygons with respect to a
common direction $d$. In a straight-line subdivision every face
has at least three edges; if all faces are convex, and all have
exactly three edges, we have
a {\it triangular subdivision}, or a {\it triangulation} of the plane.\par

\digress{In order for a straight-line subdivision to be properly convex,
monotone, or triangular, the stated property must hold also for the
infinite face(s) that constitute the ``background’’ of the subdivision.
Unfortunately, the exterior face of a bounded
subdivision satisfies neither of these properties.\par

\dp Therefore, when we are dealing exclusively with
bounded subdivisions, it is convenient to modify the definitions
given above so that the the {\it complement} of the exterior face
(i.e. the union of all finite faces) is required to be respectively convex,
monotone or triangular.}

A convex polyhedron $K$ in three-space can be represented by a convex
subdivision of the plane. The correspondence can be established
through stereographic projection: let $o$ be a corner vertex of $K$, let
$\eta$ be a supporting plane that touches $K$ only at $o$,
and let $\xi$ be the other supporting plane of $K$ parallel to $\eta$.
Now hang a light source at point $o$ so that it is just inside $K$,
and, for each point $p\neq o$ on the boundary of $K$, define its
projection $p\pr$ as being the shadow it casts on $\xi$:\fig4
It turns out that each edge of $K$
is projected into a straight segment or ray (with vertex $o\pr$ at infinity),
and each face into a convex polygon. The projections of the
vertices, edges and faces of $K$ will define a convex subdivision of
the plane $\xi$.\par

An algorithm for point location in a convex subdivision of the plane
is therefore also an algorithm for deciding point inclusion in a convex
polyhedron: if we know that $p$ is between $\eta$ and $\xi$, and if
we have located $p\pr$ is inside the projection
$f\pr$ of face $f$, we can test whether point $p$ is inside $K$
by checking whether it is on the ``interior’’ side of the supporting plane
of $f$.

The following is an important an well-known
property of planar subdivisions:\par

\theorem{5.7 {\rm (L. Euler)}}{In any planar subdivision, $nf̌-ně+nv̌=2$.}

\digress{Although this relation has been known at least
since the eighteenth century, a surprisingly long time elapsed before
mathematicians were able to provide a rigorous proof of it.
One of the several unsucessful attempts even says
``here is the proof: $\ldots$
and here are the known exceptions: $\ldots$’’!\par

\dp The theorem was usually stated for polyhedra (rather than
general plane subdivisions), and most of
the difficulty was due to the lack of a suitably rigorous
definition of such objects.The story of theorem 5.7 and its several ``proofs’’
can be found in the book {\it Proofs and Refutations} by Imre Lakatos.}

Theorem 5.7 has two important consequences:\par

\theorem{5.8}{In any triangulation $ně={3\over 2}nf̌=3nv̌-6$.}
\proof{There are three edges in each face, or $3nf̌$ in total;
but each edge belongs to two faces and therefore is counted twice, so
we have $ně={3\over 2}nf̌$. Substituting $nf̌={2\over 3}ně$
in Euler’s relation we get $nv̌-{1\over 3}ně=2$ or $ně=3nv̌-6$.}

\theorem{5.9}{In any straight-line subdivision $ně\leq 3nv̌-6$.}
\proof{It is easy to see that a straight-line subdivision with $nv̌$
vertices and maximum number of edges has to be a triangulation.
From this fact and from theorem 5.8 we conclude that
any straight-line subdivision will have $ně\leq 3nv̌-6$.}

From theorems 5.8 and 5.9 we conclude that $nv̌=\Theta(ně)$ for
straight-line subdivisions, so $nv̌$ can also be used as a measure of
the complexity of the subdivision. For triangulations, the number of
faces $nf̌$ is equally acceptable.\par

These observations are highly relevant to the point inclusion algorithm of
previous section: they say that if we decompose the polygon $H$ of $n$
vertices and its
complement into simpler polygonal regions {\it without introducing
new vertices},
the complexity of the resulting subdivision will still
be $O(n)$\quad\foot1{Note that this result holds even if
we allow the introduction of $O(n)$ new vertices.
In contrast, the decomposition into trapezoids presented in that section
could create $\Omega(n↑2)$ new vertices.}.\par

This also means that the query
time for point location in a simple polygon (or an arbitrary straight-line
subdivision) is the same as that for a triangulation with same
complexity.\par

\sect{5.4.1. The Lee-Preparata algorithm.}

Later on we will see that a simple polygon
can be decomposed into a triangulation of the plane
in $O(n\log n)$ time. To locate a point $p$ in this triangulation, we
can use the algorithm below, due to T. Lee and F. Preparata\foot2{The
original version of their algorithm was designed for
monotone subdivisions. The version given here has been
somewhat simplified for the special case of triangular ones.}.\par

Let $F1̌, F2̌, \ldotss, Fm̌$ be the faces of the given triangulation,
and let $n$ be the number of edges in it.
It can be shown (see problem 4 in the midterm) that there is
a family of polygonal chains $C1̌, C2̌, \ldotss, C{̌m-1}$ such that\par

\parindent 10pt
\def\tb{\hangindent20pt after1 }
\tb (a) each $Cǐ$ uses only edges of the triangulation, is
monotone with respect to the $y$-axis and is infinite in both
directions;\par

\tb (b) the chains are consistently ordered by increasing $x$-coordinate,
i.e. every edge of $Cǐ$ is on or to the left of $C{̌i+1}$;\par

\tb (c) the region between two consecutive chains consistrs of a
single face of the triangulation.\fig5\par
\parindent 0pt

Because of property (c), to locate a point in one of the faces $Fǐ$
requires only that we locate it between
two consecutive chains $C{̌i-1}$ and $Cǐ$\quad\foot3{In this section
the indices do {\it not} wrap around when out of range;
instead, appropriate dummy chains (or edges, vertices, etc.) must be
``extrapolated’’ in those cases. These details are a little bit messy but
should be obvious to any good programmer, so we
will omit them altogether.}; this can easily be done through
binary search on $i$. At each step of the search, we have to check
whether point $p$ is to the left or to the right of some chain $Cǐ$:
this requires another binary search along the edges of the chain,
to locate the one whose $y$-range includes $yp̌$. This
requires in $\Theta(\log n)↑2$ time in the worst case.\par

The Preparata-Lee algorithm stores the chains $Cǐ$ as a tree
whose root is the middle chain $C{̌\lfloor m/2\rfloor}$, and
whose subtrees represent the chains $\leftset C1̌, C2̌, \ldotss,
C{̌\lfloor m/2\rfloor-1}\rightset$ and $\leftset C{̌\lfloor m/2\rfloor+1},
\ldotss, Cň\rightset$, respectively. The naive way to
implement this tree could use $\Omega(n↑2)$ storage in the
worst case, since we could have $\Omega(n)$ chains,
each with $\Omega(n)$ edges in it.\par

To avoid this waste of space, we store at each node
only the edges that are not used by some node higher up in the tree.
So, each chain $Cǐ$ is represented as a list of ``proper’’ edges
$\langle (a↑i1̌, b↑i1̌), (a↑i2̌, b↑i2̌), \ldotss\rangle$,
where $y{̌a↑i1̌}\leq y{̌b↑i1̌}\leq
y{̌a↑i2̌}\leq y{̌b↑i2̌} \leq \ldotss$.\par

The subtree whose root is $Cǐ$
contains a set of consecutive chains $Cǰ, C{̌j+1}, \ldotss, Cǩ$, and
can be viewed as representing that part of the triangulation bounded
by the chains $C{̌j-1}$ and $C{̌k+1}$. These two chains are respectively
the nearest left ancestor and the nearest right ancestor of the subtree
root $Cǐ$; the edges of $Cǐ$ that are not proper must be edges
of one (or both) of these two chains.\fig4\par
In order to perform the search, besides the
list of proper edges of $Cǐ$ we need also a list of
boolean indicators $\langle L↑i1̌, L↑i2̌,
\ldotss\rangle$, where $L↑iř$ is $\prg{true}$ iff the (eventually
empty) arc
of $Cǐ$ between $b↑iř-1$ and $a↑iř$ is part of the
left boundary $C{̌j-1}$.\par

The following algorithm implements the search in such data structure:\par

\algorithm{5.2}{Point location in a triangular subdivision using monotone separators}{
\step 1. [Initialize.] {Let $j\gets1$, $k\gets m$.}
\step 2. [Test for termination.] {(At this point we know that
$p$ is between the chains $C{̌j-1}$ and $C{̌k+1}$).
If $j=k+1$, stop (point $p$ is in face $Fǩ$). Otherwise,
set $i\gets \lfloor (j+k)/2\rfloor$ and proceed.}
\step 3. [Search along chain.] {Let $\langle
(a1̌, b1̌), (a2̌, b2̌), \ldotss, (aǩ, bǩ)\rangle$ be the
proper edges of the chain $Cǐ$. Do a binary search on $r$ to
find a pair of consecutive proper edges such that $y{̌b{̌r-1}}<yp̌\leq
y{̌bř}$.}
\step 4. [Check $p$ against chain.] {If $y{̌ař}\leq yp̌\leq
y{̌bř}$, then
go to step 5 or to step 6, respectively depending on whether $p$
is to the left or to the right of the edge $(ař, bř)$.
If $y{̌b{̌r-1}}<yp̌<y{̌ař}$, go to step 5 or to step 6
depending on whether $L↑i{̌r-1}$ is $\prg{false}$ or $\prg{true}$,
respectively.}
\step 5. [$p$ is to the left of $Cǐ$.] {Set $k\gets i-1$ and return to step 2.}
\step 6. [$p$ is to the right of $Cǐ$.] {Set $j\gets i+1$ and return to step 2}}

In step 4, we may have $p$ on the edge $(ař, bř)$; if this
happens we should report the fact and stop.\par

The construction of this data structure is not as expensive as it seems:
in fact, the algorithm requested in problem 4 of the midterm
can be slightly adapted to build the data structure
above in time $O(n\log n)$. As we said before, the storage
required by it is only $O(n)$, and the query time (algorithm 5.2)
is $O(\log n)↑2$.\par

\sect{5.4.2. Kirpatrick’s algorithm.}

While the $O(n\log n)$ preprocessing time of algorithm 5.2 seems
somewhat ``reasonable’’, it is natural to ask whether its $O(\log n)↑2$
query time can be reduced further, perhaps to $O(\log n)$.
The answer is ``yes’’, but until four months ago the only algorithm
known to achieve this bound was based on
the planar graph separator theorem of R. Lipton and R. Tarjan (1979).
This theorem says that every planar graph with $n$ vertices can
be split in two pieces of roughly equal size by removing
only $O({\sqrt n}\,)$ vertices. This leads to a point location algorithm
that requires $O(n)$ space, $O(n\log n)$ preprocessing time
and $O(\log n)$ query time. We will not discuss
the details of this algorithm, because
a much simpler one has been discovered by D. Kirkpatrick (1981).
The rest of this section gives the outline of his method.\par

Let $\Sscr$ be the given straight-line subdivision of the
plane; we assume it to be bounded and to have $n$ vertices.
As we shall see later on, by adding three new vertices and
$O(n)$ edges to this subdivision
it is possible to transform it into a bounded triangulation $\Tscr$,
such none of the original vertices of $\Sscr$ (the {\it interior vertices})
is in the boundary of the exterior face of $\Tscr$.\fig4
Since each face of $\Tscr$
belongs to a unique face of $\Sscr$, locating a point in the
former will also locate it in the latter.\par

If we remove from $\Tscr$
an interior vertex $vǐ$ and all its incident edges,
the faces $Fǐ↑1, Fǐ↑2, \ldotss, Fǐ↑d$ incident to $vǐ$
will merge in a single polygon $Kǐ$, which is star-shaped with
respect to $vǐ$.\fig4
If we know that the query point $p$ is in $Kǐ$, we can locate
it in one of the $Fǐ↑r$ in $O(d)$ steps by a dumb linear search.\par

We can consider removing several interior vertices
$v1̌, v2̌, \ldotss, vm̌$ at the same time; for
example, the vertices $v1̌$, $v2̌$ and $v3̌$ in the figure above.
As long as no two $vǐ$ are adjacent, the polygons $Kǐ$
will be disjoint, and the same observation will apply: if
somehow we discover that $p$ is inside the
polygon $Kǐ$, then $p$ can be assigned to
the correct face $Fǐ↑r$ in time $O(d)$, where $d$ is the maximum
degree of the deleted vertices.\par

The polygons $K1̌, K2̌, \ldotss, Km̌$, together with any remaining
faces of the original triangulation,
define a new straight-line subdivision $\Sscr\pr$ of the plane;
we can therefore use the same method recursively to locate $p$
in the subdivision $\Sscr\pr$.
Again, by adding new edges we can decompose the latter into a
new triangulation $\Tscr\pr$ with $n-m$ vertices;
every face of it will be either a face of the original triangulation $\Tscr$,
or will belong to precisely one of the $Kǐ$.\par

By removing
some of the vertices of $\Tscr\pr$ and triangulating the
resulting subdivision $\Sscr\prr$ we get a new triangulation $\Tscr\prr$,
and so forth until we get to a subdivision with no interior vertices,
consisting only of a triangular face and its complement. This process
gives a hierarchy of triangulations and subdivisions:\fig7
\par

The point location algorithm can be rephrased as follows. Suppose
we have located $p$ in face $Kǐ$ of a subdivision $\Sscr↑{**}$,
at some level in the hierarchy other than the bottom one.
This face is either a face of the associated triangulation $\Tscr↑{**}$, or
is a star-shaped polygon composed by three of more faces
$Fǐ↑1, Fǐ↑1, \ldotss, Fǐ↑d$ of $\Tscr↑{**}$. If the latter is true,
we can locate $p$ in one of the $Fǐ↑r$ in $O(d)$ time; so, in either
case we can locate $p$ with respect to $\Tscr↑{**}$.
Since each face of $\Tscr↑{**}$ belongs to a single face of the
subdivision $\Sscr↑*$ in the level immediately below,
the location of $p$ in $\Sscr↑*$ will also be known, and
we can proceed through one more cycle.\par

In order to make this method efficient, we would like to
remove as many vertices as possible at each level, while keeping their
degrees as low as possible. The following theorem
shows that both goals can be met quite satisfactorily:\par

\theorem{5.10}{There exist contants $c$ and $d$ such that in every
bounded triangulation with $n$ interior vertices, we can
find at least $cn$ of them that are independent and have
degree at most $d$.}
\proof{Applying theorem 5.9, we easily conclude that the total
number $e$ of edges that are incident to interior vertices is at most
$3n$. If $d1̌, d2̌, \ldotss, dň$ are the degrees of the interior vertices,
we conclude $\sumǐ dǐ\leq 2e \leq 6n$. Let $d\geq6$ be an
arbitrary constant, and $\lscr$ be the number of vertices with degree
at most $d$: we have then
$$\eqalign{\sumǐ dǐ =|\sum{̌dǐ\leq d}
dǐ + \sum{̌dǐ>d} dǐ\cr\vc
\null|\geq 0+(n-\lscr)(d+1),\cr}$$
and therefore $(n-\lscr)(d+1)\leq 6n$, which implies
$$\lscr\geq{{d-5}\over{d+1}}\,n.\eqno(2)$$
Now let’s find a set of {\it independent} vertices with degrees at most $d$,
by starting with those $\lscr$ vertices and applying the greedy algorithm:
take one vertex from the set, discard it and its neighbors,
take one of the remaining vertices, and so forth until there are no more
vertices left. Since each vertex has degree at most $d$, at each iteration
we will drop no more than $d+1$ vertices from the set. Therefore,
we can repeat the iteration $\lceil \lscr/(d+1)\rceil$ times, i.e.
we can find at least $\lceil cn \rceil$
independent vertices with degree $\null\leq d$, where
$$c={{d-5}\over{(d+1)↑2}}.$$}

Therefore, if at each level of the hierarchy we select the
vertices to be removed as described in the above
proof, the second level from the bottom will have at most $(1-c)n$
interior vertices, the level above it will have at most $(1-c)↑2n$
of them, and so on. This shows
that the number of levels is logarithmic in $n$; since
$d$ is a constant, Kirkpatrick’s algorithm will take
only $O(1)$ time per level, i.e. $O(\log n)$ time per
query.\par

Furthermore, each edge appearing on the hierarchy (except for the
three on the exterior face) is removed at some level, together
with one of its endpoints. Since at that level the endpoint has degree
at most $d$, we conclude that the whole hierarchy contains at most $dn+3$
edges, and therefore can be represented in $O(n)$ space.
To build the initial triangulation $\Tscr$ requires $\Theta(n\log n)$
time in the worst case; to this we must add the time required
to build the hierarchy. But the amount of work
needed to remove each vertex and to triangulate the resulting
``hole’’ is $O(1)$, so this second term is just $O(n)$.\par

Kirkpatrick’s algorithm provides an alternative algorithm to
test whether a point is inside a convex polygon $K$. In this case,
each level of the hierarchy corresponds to a convex polygon $K↑*$, and the
level above it is obtained by removing ``every other’’ vertex
from $K↑*$:\fig6\par

Suppose we know $p$ is outside the polygon $K↑{**}$ of some
level, but inside the ``exterior’’
triangle defined by three consecutive edges, say
$\alpha, \beta$ and $\gamma$ in the following figure:\fig4
Then we have to check $p$ against the two edges $\eta$, $\epsilon$
of the polygon $K↑*$ of the level immediately below.
If $p$ is on the ``exterior’’ half-plane of both
edges, then $p$ is definitely outside the original polygon; if it
is on the ``interior’’ half-plane of both, it is definitely inside;
otherwise, we test it against the next level in the hierarchy,
and so on.\par


\vfill\eject\end