Solution: We order the vertices according to the following relation,
which defines a total

ordering of the points on the plane. Let *P =(x1, y1) *and
*Q=(x2, y2)*. Then *P* precedes *Q* if

either x*1 < x2 *or* x1 = x2 *and* y1 < y2.*

We keep the following data:

i) An ordered list (or priority queue) of all vertices of vertical segments,
*V.*

ii) An ordered list (or priority queue) of all vertices of horizontal
segments, *H*.

iii) The data consisting of horizontal segments should be searchable
under either of its

endpoints, something we can accomplishing by building two ordered dictionaries

with appropriate keys. Do the same for vertical segments.

iv) A basic event will be the *x-*coordinate of a vertical segment.
So we use the plane

sweeping paradigm.

General step: If *v *is an event (an *x-coordinate*
value from a vertical segment), select

all horizontal segments which have left endpoint to the left of *v.
*Using the endpoints

from *H *as events, check first whether these segments share the
same *y-*coordinate.

For any *y-*coordinate shared by multiple horizontal segments,
process these segments

left to right, by using the endpoints as events. Set a counter *c=1.
*As you proceed to check

for overlaps, *c *is the number of leftendpoints minus rightendpoints
found along the way.

Thus we can process endpoints rather than segments and still count
intersections correctly

by multiplying them by *c. *We just add *c* intersections
whenever we find a leftendpoint

and *c* is not 0.

Next remove from *H *all edges whose right endpoint is also the
the left of *v.*

Select all vertical segments that have *v *as coordinate of an
endpoint. Take the vertex *Bv*

with lowest *y- *coordinate and set a counter *r = 1. *
Jump to the next vertice above* Bv.* Count

how many horizontal segments have *y*-coordinates between that
of *v *and *Bv*. These are

intersections. Maintain the invariant that *r *should count the
number of bottonendpoints

minus topendpoints found along the way. Intersections shall be
counted with multiplicity
*r, *both for the overlapping of vertical segments and for crossings
of horizontal and

vertical segments.

Running time: The dictionaries could take time *O(nlog(n))*
to build. Consecutive searches

then take time* log(n)* to perform, or constant time to find the
next element. We have *O(n)*

events to process. Each of these events might take *O(k+log(n))*
to perform, where *k *is the

number of intersections associated to the event. Thus the total running
time is *O(k +nlog(n))*.

Suppose you are given a collection

"special." Design an efficient algorithm for determining if the special point can be separated

from the rest of the points in

points on the other. What is the running time of your method?

Solution: Let *P* be the special point, and *T* be a stack
containing all points of *S* except for *P*.

Then if *T* has only one element *Q* let a be the orthogonal
bisector of the segment from *P* to *Q*.

Then a is a line separating *P* and *Q*. If *T*
has at least two points, we will have to measure

angles. All angle measurements will be made with respect to *P*.
Pop *Q* and *S* from *T*

and order them as *P_1, P_2* in such a way that the angle traversed
counterclockwise from
*P_1* to *P_2* is less than half turn. If *P, P_1*
and *P_2* are colinear and *P* is in between *P_1*

and *P_2* then such angle does not exist, neither there is a line
separating *P* from *P_1* and *P_2*.

So we may assume that we can order the points as above. Let *d*
be the minimum of
*dist(P_2, P)* and *dist(P_2, P)*.

Continue, popping another point *P_k* from *T *and checking
whether:

i) *P_k* lies in the ray from *P to P_1*, or in the ray from
*P *to* P_2*, or within the convex

region described by these rays. This can be readily computed by comparing
the slope

of the segment connecting *P_k *to* P* with those of the
mentioned rays. Discard *P_k* after

replacing *d *by minimum of *d *and* dist(P_k, P).*

ii) *P_k* lies within the convex region between the rays going
from *P* in the opposite

directions of *P_1* and *P_2*, or on those rays.
Then there is no line separating *P* from the

set *{P_1, P_2, P_k}* and we are done.

iii) *P_k* lies within the convex region described by the ray from
*P* in the opposite direction

of *P_2 *and the ray in the direction of *P_1*. Then *P_k*
comes "before" *P_1*. Replace *P_1*

by *P_k*, and *d* by minimum of *d *and *dist(P_k,
P).*

iv) *P_k* lies within the convex region described by the ray from
*P* to *P_2* and the ray leaving
*P* in the opposite direction of *P_1*. Then *P_k*
lies "ahead" of *P_2*. Replace *P_2* by *P_k* and
*d *by the minimum of *d* and *dist(P_k, P).*

If we have emptied *T* and (ii) never occurred, then there is a
line separating *P* from the rest

of *S*. Let theta be half of the angle from *P_2 *to
*P_1*. So theta is an acute angle. Let *r* be the

ray bissecting the convex region described be the rays through *P_1*
and *P_2.* Trace a line

a perpendicular to *r*, and intersecting *r* at a distance
equal to *(d/2)cos(theta)* from *P*. Then

the line a separates* P *from the rest of the points.

Since each computational event was associated with processing a point
from T, plus some

constant time computations at the beginning and end, then our algorithm
runs in time *O(n)*.

Obs.: I assumed that *S *was not presorted in any fashion.
If it is, it may be possible to

use that order to find the final *P_1* and *P_2 *(giving
widest angle) in logarithmic time,

or decide that the separating line does not exist. In that case,
the whole algorithm would

also run in logarithmic time.

Suppose you are given a simple polygon

are given two points

Solution: I will first describe a method that runs in time *O(n),
*where *n *is the number of

vertices in the original polygon, and then we describe one that runs
in time *O(r)*, where r

is the number of triangles traversed in the path from *p *to
*q.*

Method 1: We translate the problem into a minimum-distance traversal
of a graph *G*.

For each triangle of given triangulation, create a vertex of *G*,
and connect two vertices of *G*

whenever the triangles they refer to share an edge in the triangulation.
So *G* is the dual

graph of the triangulation.

I claim that *G *has no cycles. This is because a cycle in
*G* defines a face in *G *and by duality,

would enclose a vertex of the original polygon. But we
are not allowed to seek paths

outside the polygon and so we will never enclose a vertex.

Since *G *is a tree, there is a unique path from the dual of *T_p,
*the triangle containing the vertex
*p, *to the dual of *T_q. *Finding the path and
storing the vertices of *G *(duals of triangles in the

given triangulation) can be done by standard continuous graph traversal
methods, such as depth

search.

In the implementation, the two steps mentioned above (creation of *G*
and traversal) should be

done simultaneously (that is, we build *G* as we make our way
from *p* in each possible

direction). Then as soon as we find one path to *q*, we
may abort the other attempts.

Running time: Building *G* and traversing it will in general
take as much time as there are edges

plus vertices in *G*. Each edge in *G *comes from an
internal edge in the original triangulation,

and since each triangle contributes with 3 edges, the number of edges
in the triangulation

(internal and external) is (three times the number of triangles + number
of vertices in

original polygon)/2. Using Euler's characteristic, we get that
the number of triangles is *n-2,*

where again *n *is the number of vertices in the polygon *P.
*The number of edges of *G *is then
*n-3. *The number of edges plus vertices in *G *is
thus *2n - 5. *Hence the running time of *O(n).*

Method 2: This method will run in time *O(r),* where *r*
is the number of triangles in the path

from *p* to *q*.

If *p* or *q* are already vertices of the original polygon,
we keep them. Otherwise we look at

the triangles *T_p* and *T_q* containing *p,
q*. (It might happen that *p* lies on an edge, and
therefore is contained in two triangles. In this case, just work
with both of them. Same

observation valid for *q*.) Next consider all vertices of
*T_p* and *T_q*, and label them
*p_1, p_2, p_3, q_1,* *q_2* and *q_3*. Starting
from each of *p_i, q_i, i=1..3,* move on each

direction along the boundary of the polygon until one of the other
points is reached.

If from *p_1* in some direction we reach another *p_i* before
any *q_j*, then just disregard

this path. As soon as a path is found from a *p_i* to a
*q_j*, stop the search, ending up with

the shortest path along the boundary of the polygon, from a *p_i*
to a *q_j*. Since we performed

at most six similar searches, the computation time up to now is of
the order of the number

of edges along this path.

Say that *p_1 > a > b > ... > z > q1* is the shortest path
above, where the intermediate letters

designate the vertices along the boundary of *P* connecting
*p_1 *to *q_1.* Then trace a segment

from* p *to *p_1*. Centered at *p_1*,
rotate the segment to *p* either clockwise or

counterclockwise, choosing the direction that will bring this segment
to lie along the edge

from *p_1* to *a *just before it swings out of the polygon.
As you move in this direction,

enqueue all triangles the segment sweeps by. Then add the triangle
with edge *p_1 - a *and

move on to the vertex *a*. Continue this sweeping action in each
vertex, hopping on to the next

vertex until you reach *q_1*. On *q_1* you do the same procedure,
finishing when you reach

triangle *T_q*. Notice that the number of operations used
to enqueue triangles is roughly

proportional to the number of triangles themselves in the path from
*p* to *q*. It is also clear

that the shortest path inside the polygon must cross this triangles
(or touch them on a vertex),

because every triangle in the triangulation of *P *touches
the boundary and the shortest path

can be "projected" onto the boundary to give the shortest boundary
path. Also since each

edge on the boundary path is the edge of a triangle in the final path,
then the total running

time is at most *O(r).*

Prove by induction (not using the master theorem) that the running time of the 2-variable linear programming algorithm is

Solution: Since we know the algorithm terminates, it solves the first
few values of *n *in *O(1)*

time. We must show the induction step.

First, our algorithm is recursive. It performs an amount of computation
which is clearly

proportional to the input size *n*, and then e xecutes a recursive
call on a problem which has

input size at most* 3n/4. *Let *c *be the constant
of proportionality that accounts for the work

done in each recursive instance. If *T *stands for
the running time, then we have:

*T(n) <= cn + T(3n/4).*

Since *3n/4 *is less than *n, *the induction hypotheses gives
*T(3n/4) *= *3bn/4, *for some constant *b.*

Thus: *T(n) <= n(c + 3b/4) <= bn.*

(As long as we are not too greedy and accept the restriction *b >
4c.*)

Suppose you are given two convex polygons

Solution: Without loss of generality, we assume that *P *is
to the left of *Q *and that the maximum
*y-*coordinate of the vertices of *P *is larger than the
corresponding coordinates of *Q. *Let *p *be

the highest vertex in *P* and *q *that in *Q. *
This can be found in *log(n_P) + log(n_Q)*, using a

binary search. *n_P *and *n_Q* are the number of vertices
in *P *and *Q, *respectively.

If the line from *p* to *q *crosses either polygon,
it will do so to the right of *p *in *P *and to the

right of *q *in *Q.* (It slants downwards from these
points.) Notice that, if the line *pq*

crosses *Q, *then the edge to the right of *Q,* if extended
as a ray towards *p, *will pass under *p*.

We search for the first edge which has positive slope, and return to
*q* in a binary search

for the first edge that when prolonged to the right, will leave some
part of *P *below.

Notice that to check whether a given prolonged edge leaves a given vertex
of *P *below

takes constant time. To check whether a given edge leaves at least
one vertex below

takes logarithmic time in *n_P, *using binary search methods.
Checking whether some

edge of *Q* leaves any of *P *below takes *O*(*log(n_P*n_Q))
=* *O(log(n_P) + log(n_Q)).*

By symmetry, we spend the same computational time to find the last edge
of *P* that will

leave some of *Q *above. A line connecting the right end vertex
of the edge found in *P *to the

left end vertex of the one found in *Q* will be the tangent sought.

Here below a view of the edge *e2* of *P *which is the last
to leave some of *Q*

above, but is preceded by *e1 *which does not have that property.
A line connecting

the vertex in between *e1* and *e2* to *q* is clearly
the tangent. (We here have changed names

and *q* refers to the vertex in *Q *having properties as
the vertex between *e1 *and *e2*.)