\input CS445Hdr
\def\file{CS445NX.tex of November 23, 1982 7:07 PM}
\def\header{Miscellaneous leftovers}
\def\title{Leftovers}
\chap{2. Minimum spanning circle.}

\lemma{2.???B}{If the points $r$ and $s$ are on opposite sides of the line $pq$, then $r$ is inside the circle $pqs$ iff $s$ is inside the circle $pqr$.}

{\bf also used in the incircle test.}

\lemma{2.???D}{Let $p, q, r$ be three non-collinear points, $C$ be their circumcircle, $H$ be the half-plane defined by $pq$ that contains $r$, and $D$ be any circle through $p$ and $q$. Let also $c$ and $d$ be the centers of $C$ and $D$, and let $\lscr$ be the ray out of $c$ perpendicular to $pq$ and pointing into $H$. Then the following conditions are equivalent:

\tp 1. $r\in D$\par
\tp 2. $C\inte H\subset D\inte H$
\tp 3. $C-H\superset D-H$.\par
\tp 4. $d\in \lscr$.

\tp Furthermore, the set inclusions are proper iff $r$ is in the interior of $D$, or iff $d$ is in $\lscr-\set{c}$.}

\lemma{2.???BB}{If the points $r$ and $s$ are on the left side of the line $pq$, then $s$ is inside the circle $pqr$ iff the circumcenter of $pqs$ lies on the ray perpendicular to $pq$, pointing away from H$, and whose origin is the circumcenter of $pqr$.}

{\bf use the preceding lemmas to show ordering of circles through $p$ and $q$. These lemmata are also used in the Voronoi chapter.}

\chap{3. Convexity.}

\lemma{3.???Q}{If the quadrilateral $\langle a,b,c,d\rangle$ is convex,
then $\bar{ac}+\bar{bd}\geq\bar{ab}+\bar{cd}$.}
\proof{???}

{\bf ??? define {\it closed set}}

\lemma{3.???I}{The intersection of convex sets is a
convex set.}

\lemma{3.???J}{The intersection of closed sets is a closed set.}

\theorem{3.???R}{If $F$ is an unbounded convex set, for any
point $p\in F$ there is a ray with origin $p$ which contains
no exterior points of $F$.}
\proof{???}

\theorem{3.???P}{Let $F$ be a convex set, and $r,s$
be two rays whose origins $p,q$ are in $F$ or on
its boundary. Then either both $r$ and $s$ meet the exterior of $F$,
or neither does.}
\proof{If $r$ and $s$ are collinear, then one of them
is contained in the other, and we have $r=pq\uni s$ (or the other way around). By theorem 3.8 the segment $pq$ contains
no exterior point of $F$, so any exterior point
belonging to one of them is in the common part, and belongs to the other too.

\hp So, let’s assume the rays are not collinear,
and let’s suppose $s$ is the only of the two that contains
exterior points. Let $x$ be such a point; by definition,
there is some ball $Sx̌$, completely exterior to $F$, with center $x$.
Let $y$ be any point of $r$, and $z$ any point of $xy$ that is in
$Sx̌$ but is distinct from $x$. Since $y$ is not collinear with $s$,
the line $\lscr$ through $q$ and $z$ is not parallel to $r$;
since $z$ is in the plane of $r$ and $s$, $\lscr$ will meet the
line of $r$ at some point $w$. From
the geometry of the construction, $z$ will be
betwen $q$ and $w$, and $w$ will be in $r$; therefore, by theorem
3.8, $z$ is either in the interior or on the boundary of $F$,
a contradiction.

\hp By the same token, $r$ cannot be the only one
to contain exterior points, so the theorem is proved.}

\theorem{3.???PR}{Given any two points $p,q$ in a
closed convex set $S$, and a direction $d$,
there is a ray $r\subset S$ from $r$ with direction $d$
if and only if
there is a ray $s\subset S$ from $q$ with direction $d$}

We say that two bundles $B,B\pr$ are {\it parallel} iff for every ray
$r\in B$ there is a parallel ray $r\pr\in B\pr$ with the same orientation,
and vice-versa. \par

Let $F$ be a convex figure. For any point
$p\in F$, let $Bp̌$ be the bundle of all rays with
origin $p$ that are contained in
$F$. We claim that

\theorem{3.???CB}{$Bp̌$ is a convex bundle; moreover, for any
other }

\theorem{3.???H}{A point $p\in P$ is on the boundary of $\hull(P)$
iff it is on a supporting line of $P$.}
\proof{???}

\theorem{3.???S}{A point $p$ is on the boundary of a convex
set $S$ if and only if there is a supporting line
$\lscr$ of $S$ passing trough $p$.}
\proof{???}

This theorem has an immediate (?) corollary:

\theorem{3.???SC}{A point $p$ is on the boundary of
$\hull(P)$ if and only if there is a supporting line $\lscr$
of $P$ passing through $p$.}

\vfill\eject

\chap{5. Point location problems.}

{\bf ??? require convex subdivisions to have strictly convex faces.}

\lemma{5.???C}{In a convex subdivision of the plane
a) all edges are straight,
b) two faces have at most one edge in common
c) finite vertices have degree three or more,
c) at most two edges of any face are incident to the same vertex.}
\proof{Let $F,G$ be the faces on either side of some edge $e$,
and $p,q$ be any points of $e$. Since $e$ is in the boundary of both
$F$ and $G$, the same is true of ???.}

\theorem{5.???B}{A convex subdivision of the plane with
$nf̌\geq3$ faces satisfies $ně\leq 3nf̌-6$, $nv̌\leq 2nf̌-4$}
\proof{By theorem 5.???A, each vertex has at least three edges incident to it
(this is true also for $\omega$, provided $nf̌\geq3$), and
each edge is incident to two vertices; therefore, we have
$ně\geq{3\over2}nv̌$. Combining this with Euler’s relation
$nf̌-ně+nv̌=2$ (Theorem 5.7), we get $nf̌-{3\over2}nv̌+nv̌\geq2$,
or $nv̌\leq2nf̌-4$. Substituting this again in Euler’s relation gives
$nf̌-ně+2nf̌-4\geq2$, or $ně\leq 3nf̌-6$.}


\sect{5.???D Data structures for planar subdivisions.}

The machine representation of a planar subdivision is by no
means a trivial problem. There are many data
structures we can use for this purpose; which of them
is best depends not only on the kind of subdivision
we have (convex, monotone, triangular, etc.), but also on the way it is going to be used. For example, if we are going to
do point location using algorithm 5.???K, we have to
use a specific data structure, namely Kirpatrick’s
hierarchical family of subdivisions.\par

Query processing is not the only operation that has to be
considered when selecting the data structure. Some applications may require the occasional insertion, deletion
or displacement of data points, or the merge of
two separate diagrams. Data structures
for which query processing is efficient (e.g, Kirpatrick’s
hierarchy) may be ill-adapted for such operations.
In fact, they are poorly adapted for almost any task
other than point location.\par

We will therefore spend some time discussing
a `general-purpose’’ data structure, that is somewhat easier to
construct, modify and traverse. The specialized data structures
required by the various point-location algorithms can be
built readily from it (or on top of it), at a cost that
is generally linear in the size of the largest structure.\par

This structure uses three kinds of nodes, for vertices, faces
and edges, respectively. Most of the information about the
subdivision resides in the edge nodes. For each edge, we
keep the following data:

\indent\bu\quad a pointer to each of its two incident vertices;

\indent\bu\quad a pointer to each of its two incident
faces;

\indent\bu\quad a pointer to the next edge in each of its two
incident faces;

\indent\bu\quad a pointer to the preceding edge in each of
its two incident faces.\par

The eight pointers above can be divided into two
symmetrical subsets, each corresponding to one of
the faces and one of the vertices incident to the edge.
To visualize this, we may consider replacing each
edge of the subdivison by a pair of directed edges,
incident to the same two vertices but directed in
opposite directions, and each associated to the face
that lies at its left.\fig4
Each {\it directed} edge, as for example $c\pr$ in the
diagram at the right, is represented by a node
with five pointers:

\indent\bu\quad a pointer $\prg{Dest($c\pr$)}$ to the destination vertex $v$;

\indent\bu\quad a pointer $\prg{RFace($c\pr$)}$ to the face
$G$ at the right of $c\pr$;

\indent\bu\quad a pointer $\prg{FNext($c\pr$)}$ to
the edge that follows $c\pr$ in counterclockwise order along
the left face $F$;

\indent\bu\quad a pointer $\prg{VPrev($c\pr$)}$ to the outgoing
edge $d\prr$ that immediately precedes $c\pr$ in counterclockwise order around its origin $u$.\par

\indent\bu\quad a pointer $\prg{Sym($c\pr$)}$ to the
edge $c\prr$ with same endpoints and opposite direction.\par

A vertex $u$ is represented by a node
containing the coordinates of $u$ and
a pointer $\prg{Edge($u$)}$ to one of its {\it outgoing}
directed edges, say $c\pr$ in the example above. A face $F$
is represneted by a node with a pointer $\prg{Edge($F$)}$ to one of the directed edges
on its boundary (like $c\pr$ in the example) that is oriented counterclockwise around the face.\par

It is easy to check that, given any directed edge, we
can move to a ``neighboring’’ element (edge, vertex or
face), in any direction, with a constant number of
operations. For example, in the figure above the following
relations hold:

\indent\bu\quad $a\pr=\prg{FNext($c\pr)}$;

\indent\bu\quad $b\pr=\prg{VPrev(Sym($c\pr))}$;

\indent\bu\quad $d\pr=\prg{Sym(VPrev($c\pr))}$;

\indent\bu\quad $e\pr=\prg{FNext(Sym($c\pr))}$;

\indent\bu\quad $u=\prg{Dest(Sym($c\pr))}$;

\indent\bu\quad $F=\prg{RFace(Sym($c\pr))}$.\par

As a more complex example, the following program
fragment enumerates the neighbors of a given vertex
$u$, in counterclockwise order:

{\prog
$e0̌$ \pgets $e$ \pgets Edge($u$);
do
Visit (Dest($e$));
$e$ \pgets FNext(Sym($e$))
od until $e=e0̌$
\endprog}

There are of course many variants of this data structure;
for example, we could have replaced the field $\prg{VPrev($e$)}$ by the pointer $\prg{FPrev($e$)}=\prg{Sym(VPrev($e$))}$, or replaced
$\prg{RFace($e$)}$ by $\prg{LFace($e$)}=\prg{RFace(Sym($e$))}$,
without major effects on the algorithms using the
structure.\par

The vertex and face nodes may contain extra information,
e.g. the ``label’’ of the face (to be assigned to the query
points that fall in it). One may also consider linking all
vertices (and similarly all faces and all edges) in a
linear list, to simplfy their enumeration. However,
such links add to the complexity of
constructing and modifying the data structure,
so in general it is better to enumerate the structure
elements by any of the well-known graph-traversal
algorithms, that run in $O(n)$ time anyway.\par

To each vertex there corresponds a unique circular list
of edges (linked by the $\prg{VPrev}$ field), and the
same is true for each face (with $\prg{FNext}$) as the
link). If we store in each edge the
parameters of its supporting line, and the label of the
corresponding face, we can in principle do without
the vertex and face nodes. We can get
the endpoints of an edge by computing
its intersection with adjacent edges\foot1{We may get into
trouble if the faces are allowed
to have flat interal angles. Convex subdivisions
are exempt from this problem, however.} To refer to a face, we use
a pointer to one of its edges, and the same for vertices.
This probably doesn’t save us any space, but simplifies
the programs by reducing the number of record types and
the allocation procedures.\par

This data structure can be further simplified in some
special cases. In a triangulation, we can do without
the field $\prg{VPrev($e$)}$ by computing instead
$\prg{Sym(FNext(FNext($e$))}$, i.e. by going around
the left face of $e$. Conversely, if every vertex has
degree three, we can replace $\prg{FNext($e$)}$ by
$\prg{VPrev(VPrev(Sym($e$))}$. In either case
we are left with four pointers per edge node.

\vfill\eject\end