1988 Tarjan Van Wyk

SIAM J. COMPUT.
(C) 1988 Society tbr Industrial and Applied Mathematics

Voi. 17, No. I, February 1988 010
AN O(n log log n)-TIME ALGORITHM FOR

TRIANGULATING A SIMPLE POLYGON*
ROBERT E. TARJANf* AND CHRISTOPHER J. VAN WYK"
Abstract. Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the
polygon into n-2 triangles by adding n-3 nonintersecting diagonals. We propose an O(n log logn)-time
algorithm for this problem, improving on the previously best bound of O (n log n) and showing that triangu-
lation is not as hard as sorting. Improved algorithms for several other computational geometry problems,
including testing whether a polygon is simple, follow from our result.
Key words, amortized time, balanced divide and conquer, heterogeneous finger search tree, homogene-
ous finger search tree, horizontal visibility information, Jordan sorting with error-correction, simplicity test-
ing
AMS(MOS) subject classifications. 51M15, 68P05, 68Q25
1. Introduction. Let P be an n-vertex simple polygon, defined by a list

Vo,V vn- of its vertices in clockwise order around the boundary. (The interior
of the polygon is to the right as one walks clockwise around the boundary.) We
denote the boundary of P by 0P. We assume throughout this paper (without loss of
generality) that the vertices of P have distinct y-coordinates. For convenience we
define vn V o. The edges of P are the open line segments whose endpoints are vi,vi+l
for 0 < < n. The diagonals of P are the open line segments whose endpoints are
vertices and that lie entirely in the interior of P. The triangulation problem is to find
n-3 nonintersecting diagonals of P, which partition the interior of P into n-2 trian-
gles.
If P is convex, any pair of vertices defines a diagonal, and it is easy to triangulate
P in O (n) time. If P is not convex, not all pairs of vertices define diagonals, and even
finding one diagonal, let alone triangulating P, is not a trivial problem. In 1978,
Garey, Johnson, Preparata and Tarjan [10] presented an O (n log n)-time triangulation
algorithm. Since then, work on the problem has proceeded in two directions. Some
authors have developed linear-time algorithms for triangulating special classes of
polygons, such as monotone polygons [10] and star-shaped polygons [31 ]. Others have
devised triangulation algorithms whose running time is O (n log k) for a parameter k
that somehow quantifies the complexity of the polygon, such as the number of reflex
angles [13] or the "sinuosity" [5]. Since these measures all admit classes of polygons
with k 1 (n), the worst case running time of these algorithms is only known to be
O(n log n). Determining whether triangulation can be done in o (n log n) time, i.e.
asymptotically faster than sorting, has been one of the foremost open problems in
computational geometry.
In this paper we propose an O (n log logn)-time triangulation algorithm, thereby
showing that triangulation is indeed easier than sorting. The paper is a revised and
corrected version of a conference paper [27] which erroneously claimed an O (n)-time
algorithm. The goal of obtaining a linear-time algorithm remains elusive, but our
*Received by the editors September 8, 1986; accepted for publication (in revised form) April 29,
1987. Typeset on July 28, 1987 at AT&T Bell Laboratories, Murray Hill, New Jersey.
’AT&T Bell Laboratories, Murray Hill, New Jersey 07974.
*Department of Computer Science, Princeton University, Princeton, New Jersey 08544. The work of
this author was partially supported by National Science Foundation grant DCR-8605962.
143
144 R. E. TARJAN AND C. J. VAN WYK
approach suggests some directions in which to look and clarifies the difficulties that
must be overcome.
The starting point for our algorithm is a reduction of the triangulation problem to
the problem of computing visibility information along a single direction, which we take
to be horizontal. A vertex-edge visible pair is a vertex and an edge that can be con-
nected by an open horizontal line segment that lies entirely inside P. Similarly, an
edge-edge visible pair is a pair of edges that can be connected by an open horizontal
line segment that lies entirely inside P. Fournier and Montuno [9] showed that tri-
angulating P is linear-time equivalent to computing all vertex-edge visible pairs. The
reduction of triangulation to computing visible pairs was independently obtained by
Chazelle and Incerpi [5]. What we shall actually produce is an O (n log log n ) -time
algorithm for computing visible pairs, which by this reduction leads to an
O (n log log n)-time triangulation algorithm.
Our visibility algorithm computes not only vertex-edge visible pairs but also possi-
bly some edge-edge visible pairs. It is reassuring that the total number of visible pairs
of either kind is linear.
LEMMA 1. There are at most 2n vertex-edge visible pairs and at most 2n edge-
edge visible pairs.
Proof. Each vertex can be in at most two vertex-edge visible pairs, for a total
over all vertices of at most 2n. Partition P into trapezoids and triangles by drawing a
horizontal line segment between each visible pair (of either kind) through the interior
of P. (See Figure 1.) Each edge-edge visible pair corresponds to the bottom boun-
dary of exactly one such trapezoid or triangle, the top boundary of which is either one
or two line segments corresponding to vertex-edge visible pairs (in the case of a tra-
pezoid) or a vertex that is in no visible pairs (in the case of a triangle). A vertex
FIG. 1. A simple polygon P, showing visibility information: dashed horizontal lines correspond to
vertex-edge visible pairs; dotted horizontal lines correspond to edge-edge visible pairs.
TRIANGULATING A SIMPLE POLYGON 145
gives rise to at most two top boundary segments of trapezoids or to at most one top
boundary of a triangle. Thus there are at most 2n trapezoids and triangles whose bot-
tom boundaries correspond to edge-edge visible pairs, and hence at most 2n such pairs.
The second cornerstone of our method is the intimate connection between visibil-
ity computation and the Jordan sorting problem. For a simple polygon P and a hor-
izontal line L, the Jordan sorting problem is to sort the intersection points of OP and
L by x-coordinate, given as input only a list of the intersections in the order in. which
they occur clockwise around t)P. (The list of vertices of P is not part of the input.)
Hoffman, Mehlhorn, Rosenstiehl and Tarjan 14] have presented a linear-time Jordan
sorting algorithm, which actually works for any simple curve, open or closed. This
algorithm, which we call "the Jordan sorting algorithm," requires that OP actually
cross L wherever it touches it, but the algorithm is easily modified to handle tangent
points, provided that each intersection point is labeled in the input as being either
crossing or tangent.
Computing visible pairs is at least as hard as Jordan sorting, in the sense made
precise in the following lemma:
LEMMA 2. Using an algorithm to compute vertex-edge visible pairs, one can
solve the Jordan sorting problem for an n-vertex polygon P in 0 (n) additional time,
given as input the polygon and the line L (and not the intersections).
Proof. Compute all vertex-edge visible pairs for P. Next, turn P "inside out" by
breaking P at its lowest vertex and drawing a box around it as shown in Figure 2,
forming a polygon Q with n+5 vertices. Compute the vertex-edge visible pairs for Q.
These pairs specify vertex-edge visibilities on the outside of P, and indicate which ver-
tices of P can see arbitrarily far left or right on the outside. Partition the inside and
outside of P into trapezoids, triangles, and .unbounded trapezoidal regions by drawing
horizontal line segments corresponding to each visible pair. Given a line L, the inter-
section points of OP and L can be read off in increasing x-order by moving left to
right through the regions that intersect L. The total time for this algorithm, not
including the two visibility computations, is O (n). rn
Since any visibility computation does Jordan sorting implicitly, it is natural to try
using Jordan sorting explicitly to compute visible pairs. This leads to the following
divide-and-conquer visibility algorithm (see Figure 3)"
Step 1. Given P, choose a vertex v of P that does not have maximum or
minimum y-coordinate. If no such v exists, stop: there are no visible pairs to compute.
Otherwise, let L be the horizontal line through v.
Step 2. Determine the intersection points of 0P and L in the order in which they
occur along the boundary of P.
Step 3. Jordan sort the intersection points and report the visible pairs that
correspond to consecutive intersection points along L.
Step 4. Slice P along L, dividing P into a collection of subpolygons.
Step 5. Apply the algorithm recursively to each subpolygon computed in Step 4.
The Jordan sorting algorithm has the fortuitous side effect of computing enough
extra information so that Step 4 is easy. The hard part of the computation is Step 2.
There are two major bottlenecks in the algorithm, either of which will make a naive
implementation run in quadratic time. First, it is possible for the algorithm to report
redundant visibility pairs; indeed, the example in Figure 4 shows that it can report
fl (n 2) nondistinct pairs.
We eliminate this bottleneck by modifying Step 2 to compute only some of the
intersections of 0P with L. This can cause the Jordan sorting algorithm used in Step
FIG. 2. Polygon P of Figure turned "’inside out," and showing exterior vertex-edge visible pairs.
3 to detect an error, since the sequence to be sorted need no longer consist of all inter-
sections of a simple polygon with a line. Fortunately the sorting algorithm is incre-
mental, and when it detects an error, we can restart it in a correct state by computing
a few additional intersections and making local changes in its data structure. We call
this augmented sorting method Jordan sorting with error-correction.
By computing only some of the intersections of 3P and L and using Jordan sort-
ing with error-correction, we obtain a visibility algorithm that reports only O (n) visi-
ble pairs and runs in O (n) time not counting the time needed to find intersections.
This approach requires the use of a two-level data structure to represent polygon
boundaries, but imposes no further constraints on the details of the data structure.
The second, far more serious bottleneck is the problem of actually finding the
intersections. The line L divides 0P into pieces. If each of these pieces ended up in a
different subpolygon boundary, then we could obtain (with a little work) an overall
O (n) time bound for the visibility algorithm by using finger search trees in the boun-
dary data structure and appealing to the linearity of the following recurrence [20, p.
185]:
T (n)
]O(1) if n-- 1;
/ max {T(k)
I,l<k <n
+ T(n-k)+O(1 +logmin{k, n-k})} ifn>l.
Unfortunately the pieces of the original boundary do not stay apart but are
regrouped to form the subpolygon boundaries. To beat the O (n log n) time bound of
previous triangulation algorithms, we need another idea, that of balanced divide and
conquer. We refine the visibility algorithm to choose L judiciously, so that each of the
subpolygon boundaries contains a relatively small number of pieces of the original
STEP
FIG. 3. Illustrating Steps and 4 of the visibility algorithm.

boundary. Balanced divide and conquer combined with the use of finger search trees
in the boundary data structure produces a visibility algorithm that runs in
O (n log log n) time.
The remainder of this paper consists of five sections and an appendix. In Section
2 we review the Jordan sorting algorithm and modify it to do error-correction. In Sec-
tion 3 we present a generic visibility algorithm, based on Jordan sorting with error-
correction, that reports O(n) visible pairs. In Section 4 we refine the algorithm so
that it uses balanced divide and conquer. In Section 5 we propose a data structure for
representing the polygon boundary that consists of two levels of finger search trees.
We show that with this data structure the visibility algorithm of Section 4 runs in
O (n log log n) time. We close in Section 6 with some remarks, applications, and open
problems. The appendix contains a discussion of finger search trees, which are needed
not only in the visibility algorithm itself but also in the Jordan sorting algorithm.
2. Jordan sorting with error-correction. Let P be a simple polygon and let v be a
vertex of P. Let L be the horizontal line through v, and let Xo v, x,... ,Xm- be
the intersection points of igP and L in clockwise order around igP. (Since throughout
this paper we are assuming that the vertices of P have distinct y-coordinates, igP and
FIG. 4. This class of polygons can cause the naive algorithm to produce a quadratic amount of out-
put. Afirst slice through v 0 cuts off k + triangles. Successive slices at v,., i--l, 2 k, report
k- + visible pairs, but only two are new each time.
L intersect in a finite set of points.) Points X l,X 2 ,Xm_ are crossing points of OP
and L; point x0 is either a crossing point or a tangent point. We impose a total order
on the points xi given by the order of their x-coordinates. We wish to sort
X o,Xl, Xm- according to this total order.
The sequence Xo,Xl Xm-1 gives rise to two forests, in the following way.
For convenience let Xm X o. Without loss of generality assume that the part of 0P
from x0 to X lies above L. For O<i<m, let ei=min{xi_,xi} and
ri max{xi-l,Xi}. We say a pair {Xi-l,Xi} encloses a point x if gi < x < ri. We say
two pairs {Xi-l,Xi} and {X-l,X} cross if {Xi-l,Xi} encloses exactly one of xj-1 and x;
{Xi-l,Xi} encloses {xj_,x} if it encloses both of x._l and xj_. The simplicity of P
implies that if i----j mod2, then the two pairs {Xi-l,Xi} and {xj_,xj} do not cross.
We call this the noncrossing property. The Hasse diagram of the "encloses" relation
on the set of pairs {{x2,x2i+}lO < < m12} is a forest, called the upper forest. The
Hasse diagram of "encloses" on the set of pairs {{x2i-l,X2i}]O < < rnl2} is also a
forest, called the lower forest. We order each set of siblings in either forest by plac-
ing {xi-,xi} before {Xj_l,Xj} if r < gj. This makes each forest into an ordered
forest. We make the two forests into trees by adding the dummy pair {-oo, oo} to
each. Thus we obtain two trees, called the upper tree and the lower tree. (See Figure
5.) We call the set consisting of a parent in either tree and its children a family.
UPPER TREE"
2
- m
14
12
11 10
LOWER TREE"
FIG. 5. Hasse diagram of the "’encloses" relation with respect to line L. (Point xi is labelled i.)
We shall restate the Jordan sorting algorithm [14] in a form suitable for exten-
sion to the visibility computation. The algorithm proceeds incrementally, processing
the points X l,X 2 ,xm one at a time and building the upper tree, the lower tree,
and a list of the points in sorted order. Initialization consists of making {-oo, oo} the
only pair in both trees and defining the sorted list to be (-oo,x0,oo). The general step
consists of processing point xi by performing the following steps. Suppose is odd, i.e.
{xi-,xi} is to be added to the upper tree. Assume xi- < xi. (The case xi- > xi is
symmetric.)
Step 1. Find the point x that follows x_ in the sorted list.
Step 2. Find the pair {xj_,xj} in the upper tree such that x E {xj_,xj}.
Step 3. Apply the appropriate one of the following four cases (see Figure 6):
Case A (,aj < xi- < rj < xi). Halt: {xi-,xi} and {Xj-l,Xj} cross.
Case B (gj <xi- <xi <rj). Make {x_,xi} the new last child of
{x)_,x)}. If < m, insert xi after xi-1 in the sorted list.
150 R.E. TARJAN AND C. J. VAN WYK
L
,j rj
= =L
Lj j..,_,x
FIG. 6. The four cases for Jordan sorting.
<
Case C (xi ). Insert {Xi_l,Xi} into the list of siblings of {Xj_l,Xj} just
before {x_,xj}. If < m, insert xi after xi- in the sorted list.
Case D (xi_ < j < xi). In the list of siblings of {x_],xj}, find the last
one, say {Xk-l,X,}, such that k < Xi. If rk > Xi, halt: {xi-,xi} and {Xk_I,X k}
cross. Otherwise, if {Xk_I,X k} is the last child of its parent pair {xp_,xp} and
rp < xi, halt: {xi-,xi} and {Xp_l,Xp} cross. If neither of these crossings is found,
remove from the list of siblings of {xj_],xj} the sublist from {Xj_l,X} to
{Xk_I,X k} (inclusive) and replace it by {xi-],xi}. Make the removed sublist the
- list of children of {Xi_ 1,xi}. If < m, insert xi after rk in the sorted list.
Observe that if {Xi-l,Xi} and {Xj_l,Xj} are two pairs with
j mod 2, all four points xi-,xi, x_,xj are distinct unless
> j and
m and tn is odd,
in which case possibly xi c: {xj_,xj}. This means that Cases A-D exhaust the possi-
ble ordering relationships among the four points.
If is even, i.e. {xi-,xi} is to be added to the lower tree, the processing is analo-
gous to the above, with a few changes needed to accommodate the fact that Xo is in
no pair in the lower tree until xm x0 is processed (if then). The changes are as fol-
lows:
(i) Just before Step 2, if x x0, replace x by the point that follows x0 in the
sorted list.
(ii) In Step 2, find the pair {xj_,xj} that contains x in the lower tree (instead of
in the upper tree).
(iii) In Step 3, Cases B and C, if xi-i < Xo < xi, insert xi in the sorted list
after X o (instead of after Xi_l).
(iv) In Step 3, Case D, if rk < X o < xi, insert xi in the sorted list after X o
(instead of after rk).
The sorting algorithm as stated tests for crossing pairs. If the input is guaranteed
to be correct (i.e. to have the noncrossing property), we can simplify the algorithm by
eliminating Case A and the two tests for crossing pairs in Case D.
Making the algorithm run in linear time requires the use of appropriate data
structures. Each list of siblings in the upper and lower trees is represented by a homo-
geneous finger search tree (see the appendix) in which each leaf is a pair in the list.
In addition, there are bidirectional pointers between each pair and its first and last
children (in whichever tree contains the pair). Thus each family forms a doubly-
linked circular list, with the additional property that any pair in the list can be
accessed from any other pair d away in either direction in O (1 + log d) time. Furth-
ermore the amortized time to insert a pair next to a given one in a family list is
O (1), and the amortized time to remove a sublist of d pairs from a list of s pairs,
given the end pairs of the sublist, is O (1 + log(min {d, s-d} + 1)).
The running time of the. Jordan sorting algorithm is dominated by the time spent
doing "remove a sublist/insert a pair" operations on family lists. Let T (p,s) be the
maximum amortized time needed to do a total of/9 such operations on an initial list of
size s and on the removed sublists. Then T (p,s) obeys the following recurrence:
0 ifp =0;
(2) T(p,s) max {T(i,d+l)
/O<i<p
+ T(p-i-l,s-d+l)
[o<d + 0 (1 + log (min {d, s -d} + 1))} if p > O.
A proof by induction shows that T (p,s) O (p +s). The list manipulation time
of the Jordan sorting algorithm is at most T([m/2], 1) + T([ml2], 1), from whicli it
follows that the algorithm runs in O (m) time. For further details of the algorithm
and the analysis see the original paper [14]. (In our restatement of the algorithm, we
have modified the data structure slightly, the main change being to eliminate circular
level links in the finger search trees. These changes do not affect the O (m) time
bound.)
We now want to augment the Jordan sorting algorithm so that when it detects
two crossing pairs, it can in certain cases restart itself in a corrected state that
represents the partial sorting of a sequence modified to eliminate the crossing. In the
application of Jordan sorting to the visibility computation, the sorting algorithm
receives as input only a possibly noncontiguous subsequence of the sequence of inter-
sections. In this subsequence, certain pairs are designated as special. (All other pairs
are normal.)
To accommodate the operation of the triangulation algorithm, we impose on each
special pair {xi-,xi} the additional requirement that it enclose no given intersections
other than xi-1 and xi. We call this the nonenclosure property. On the other hand,
special pairs are potentially modifiable: if {xi-,xi} is a special pair, there may be
additional intersections between x-i and x; along 0P. The Jordan sorting algorithm
is allowed to request such additional intersections if it detects a crossing or a violation
of the nonenclosure property.
The mechanism for providing additional intersections is a procedure named refine,
whose input parameters consist of a special pair {Xi-l,Xi} and a point x enclosed by
Amortized time is the time per operation averaged over a worst-case sequence of operations that
begins with an empty data structure. For a discussion of this concept see the first author’s survey paper
[261.
{Xi_l,)i}. The procedure returns a bracketing pair x’,x" such that x’ and x" are
intersections of igP and L, the four intersections occur in the order xi-,x’,x",xi along
0P, and the five points occur in the order xi_,x’,x,x",xi (or its reverse) along L. If
there is no such pair, refine returns nothing. If a pair is returned, the new sequence to
be sorted is the old sequence with x’ followed by x" inserted between xi- and xi. Of
the three pairs that replace {xi-,xi}, the pairs {Xi-l,X’} and {x",xi} are special and
the pair {x’,x"} is normal. (This means that {x’,x"} is the closest pair of intersec-
tions to x.)
We shall modify the Jordan sorting algorithm so that it can handle special pairs,
using refine when possible to eliminate violations of the noncrossing and nonenclosure
properties. The modification consists of the following three additions to the algorithm
(see Figure 7):
(i) In Step 1, if {x_,xi} is special and x < xi, call refine ({xi_,xi},x). If
refine returns no pair, halt: {Xi-l,Xi} violates the nonenclosure property. If refine
returns a pair (x’,x"), insert x’ and x" in the sequence to be sorted between xi- and
xi and restart the processing with x’.
(ii) In Step 3, Case B, if {xj_,xj} is special, halt: the nonenclosure property has
been violated. Even if it can be restored by refining {xj_,xj}, this will produce a vio-
lation of the noncrossing property. (This also happens in Step 3, Case A: even if
FIG. 7. Modifications to make Jordan sorting error-correcting.

{Xj__,Xj} is special and the crossing of {Xi_l,Xi and {Xj_l,Xj} can be eliminated by
refining {xj_,xj}, this will produce a new crossing pair.)
(iii) In Step 3, Case D, if {xk-,Xk} is special and rk > Xi, do not halt, but
instead call refine ({Xk-l,Xk}, xi). If refine returns no pair, halt: {Xk-m,Xk} violates
the nonenclosure property. If refine returns a pair (x’,x"), replace {X,-l,Xk} in the
-
upper forest by {Xk-,x’} followed by {x",Xk}. Insert {x’,x"} in the appropriate place
in the lower forest (as a sibling or child of the pair containing x, whichever is
appropriate). Proceed as in the remainder of Step 3, Case D, using {Xk-l,X’} in place
of {x_,x} and also in place of {x. 1,x.} J if {x_- l,x.}---{xk ,x’} That is, if
I J
{Xj-l,Xj} {Xk-,Xk}, replace {X_l,X in its list of siblings by {xi-,xi} and make
{xj_,x’} a child of {xi-,xi}. if {xj_,xj} ; {Xk-l,Xg}, replace the sublist from
{Xj_l,Xj} to {Xk-,x’} (inclusive) by {Xi-l,Xi}, and make the sublist the list of chil-
dren of {xi-,xi}. In either case insert xi after x’ in the sorted list (or after x0 if
x’ < Xo < x).
The correctness of the error-correcting Jordan sorting algorithm follows from the
observation that, while the algorithm is running, a special pair {x_,xj} can enclose at
most one intersection point xi q {x_,x}. To see this, suppose without loss of gen-
erality that {x_,xj} is a pair in the upper tree. An intersection xi {xj_,xj} can be
inserted between xj-1 and x in the sorted list because of the addition of a pair
{xi-,xi} to the lower tree, but the violation of the enclosure property will be detected
when the point xi+ is processed, as illustrated in Figure 7(ii).
The additions necessary to make the algorithm error-correcting cost only O (1)
time per point processed and per refinement, not including the time spent inside calls
of refine. (There are at most two insertions in sibling lists per refinement.) Thus the
error-correcting algorithm runs in O (m) time, where m is the number of intersection
points in the final refined sequence. In the next section, we shall see how error-
correcting Jordan sorting can be used to compute visible pairs.
3. An efficient visibility algorithm. Our algorithm for computing visible pairs fol-
lows the outline laid out in Section 1. It is a divide-and-conquer method that cuts up
the original polygon into subpolygons, cuts these into smaller subpolygons, and so on,
until none of the subpolygons can be further divided. In order to present the details of
the method, we must first discuss the structure of the subpolygons, which we call visi-
bility regions. The interior of a visibility region is a simply connected subset of the
original polygon interior contained between two horizontal lines, denoted by y ---Ymin
and y---Ymax (with Ymin < Ymax)" We require that the region boundary actually
intersect both of these lines. (See Figure 8.)
The boundary of a visibility region consists of connected pieces of the boundary of
the original polygon, called boundary segments, alternating with segments of the lines
Y Y min and y---Ymax. Each such horizontal segment that is not a single point
corresponds to a visible pair. At most one vertex of the original polygon lies on each
of the lines y--Ymin and y--Ymax. Although a visibility region is itself a simple
polygon, when we speak of its vertices we mean only those that are vertices of the ori-
ginal polygon P. A boundary segment begins with a vertex or part of an edge, called
a partial edge, and ends with a vertex or partial edge. We call the edge of the origi-
nal polygon that contains such a partial edge an end edge of the segment.
We divide the boundary segments into three types:
top: no end edge or vertex intersects the line y Y min;
bottom: no end edge or vertex intersects the line y Ymax;
side: one end edge or vertex intersects the line y --Ymax and one intersects the
line y y min"
Y =Ymax TOP TOP TOP
Y =Ymin
BOTTOM
FIG. 8. Schematic illustration of a visibility region. Each curve represents a segment of the polygon
boundary.
The degenerate case of a top or bottom boundary segment is a single vertex and
no partial edges; the degenerate case of a sde boundary segment is a single partial
edge and no vertices. Clockwise around the boundary of a region, the boundary seg-
ments consist of four contiguous parts: a set of top segments, which together with the
adjacent pieces of the line y -Ymax forms the top of the boundary; a side segment,
which forms the right side of the boundary; a set of bottom segments, which together
with the adjacent pieces of the line y --Ymin forms the bottom of the boundary; and
another side segment, which forms the left side of the boundary. Both side segments
must be present; either the top or the bottom or both can be empty.
We shall represent a visibility region by specifying Y min and Y max and the four
parts of the boundary (left, right, top, and bottom). We represent the top and the
bottom by lists of the boundary segments they contain, in clockwise order around the
boundary. We represent the left and right sides by their single boundary segments.
Finally, we represent each boundary segment by a list of the vertices in it, in clockwise
order around the boundary, together with its end edges (if any). We leave unspecified
the implementation of the lists that represent the boundary segments and the top and
bottom boundaries of the region; this is the topic of Section 5.
Having discussed the structure of visibility regions, we now need to introduce
some terminology concerning the intersections of the boundary of a region with a hor-
izontal line. (See Figure 9.) Let V be a visibility region and let L be a horizontal line
that intersects its interior. We partition the boundary segments of V into three types,
depending on their relationship to L:
shallow: a segment that does not intersect L;
MIX MIXED
EEP X
FIG. 9. Illustrating three kinds of boundary segment. The top group includes a deep section of three
segments. Both top and bottom groups include shallow sections of two segments.
deep: a top segment whose vertices are all strictly below L or a bottom segment
whose vertices are all strictly above L;
mixed: any other segment.
A side segment is definitely mixed; a top or bottom segment can be of any type.
We define a shallow section to be a (contiguous) sublist of shallow boundary segments
in the list of boundary segments clockwise around 0V; we define a deep section simi-
larly. A deep or shallow section consists entirely of top segments or entirely of bottom
segments. Each of the partial edges of a deep section intersects L and these are the
only intersections of the section with L. We classify the intersections of 0V with L
into two types:
nonessential: an intersection within a maximal deep section that is not the first or
the last within the section;
essential: any other intersection.
The last issues we must discuss before presenting the visibility algorithm are the
notion of a special pair and the effect of the refine procedure, both of which affect the
running of the error-correcting Jordan sorting algorithm. A pair of intersections of igV
and L is special if the intersections are the first and last in some deep section (along
O V) and normal otherwise. (Observe that the intersections of a deep section with L
occur in the same order along L as they do along igV, or in reverse order.) A call
refine ({xi-,xi}, x) has the following effect. Points xi- and xi are the first and last
intersections in some deep section, say S. If S can be split into two deep sections S
and $2 with first and last intersections xi_,x’ and x",xi, respectively, such that
{x’,x"} encloses x, then refine returns (x’,x"). If S cannot be so split, refine returns
no pair. Observe that if a pair (x’,x") is returned, {xi_,x’} and {x",xi} are special
pairs and (x’,x") is a normal pair, as required by the Jordan sorting algorithm.
There is one more crucial observation about special pairs. Consider a special pair
{xi-,xi} that comprises the first and last intersections of a single deep boundary seg-
ment. If the segment is a top segment T, then T together with the appropriate seg-
ment of the line y Y max forms a simple closed curve whose interior contains the line
segment joining xi- and xi and whose exterior contains the boundary of V other than
T. By the Jordan curve theorem, {Xi-l,Xi} can enclose no intersections other than
xi- and xi. Thus every special pair either can be refined or has the nonenclosure
property, as required by the Jordan sorting algorithm.
We are at last ready to discuss the visibility algorithm itself. The input to the
algorithm is a single visibility region V. To apply the algorithm to the original
polygon, we convert the polygon into a visibility region by dividing its boundary into
two side boundary segments whose end vertices are the vertices of minimum and max-
imum y-coordinate. The y-coordinates of these two vertices become Y min and Y max for
_
the region. The algorithm is the same as that in Section except that it computes
only the essential intersections of 0V and L in Step 2 and uses Jordan sorting with
error-correction in Step 3. That is, it consists of the following five steps"
Step 1. Given V with bounding lines y Ymin and y Ymax, choose a vertex of
V having y-coordinate Y eut such that Y min < Y cut < Y max" If there is no such v, stop:
there are no visible pairs to compute. Otherwise, let be the line y Ycut.
Step 2. Find the essential intersections of 0V and L in the order in which they
occur along 0V.
Step 3. Use Jordan sorting with error-correction to sort by x-coordinate the
essential intersections and any others introduced by refinement. Report the visible
pairs corresponding to consecutive sorted intersections along L.
Step 4. Slice V along L, dividing V into a collection of subregions.
Step 5. Apply the algorithm recursively to each subregion formed in Step 4.
The observations made above concerning special pairs and refinement imply that
the Jordan sorting step works correctly; any nonessential intersection occurs along 0V
between the members of a special pair and is available by refinement if needed.
The last detail we must fill in before undertaking an analysis of the algorithm is
the effect of Step 4. The boundaries of the subregions are formed as follows. (See
Figure 10.) Split 0V at each of the intersections sorted in Step 3. Each of the pieces
so formed corresponds to a pair in the upper or lower tree constructed by the Jordan
sorting algorithm. Each family in each of the trees whose parent has odd depth
(counting the dummy roots as being of depth zero) corresponds to a subregion. The
boundary of the subregion consists of the pieces of O V that correspond to the pairs of
the family, in the order in which the members of the family occur in the family list in
the lower tree or the reverse of this order in the upper tree, interspersed with appropri-
ate segments of the line y -Y cut, with one crucial exception: if D is a piece of 0V
that corresponds to a deep boundary section, before using D as part of a subregion
boundary, each of its segments of the line y y min or y )’max must be replaced by a
corresponding segment of the line y---Y cut. Observe that this has no effect on the
representation of the deep boundary section, which means that no change in the data
structure representing the section is necessary. Furthermore the visibility regions cut
off by this replacement and henceforth ignored are trapezoids, on which the visibility
algorithm would terminate in Step 1 were it invoked on them. The visibility algorithm
obtains its efficiency by avoiding any computation associated with these trivial tra-
pezoids.
We define Y min and Y max for the subregions as follows. Consider a subregion
above L, which corresponds to a family in the upper tree. The value of Y min for this
subregion is Y cut. The value of Y max for the subregion is Y max for the region if the
parent of the family is at depth one in the upper tree, or otherwise the maximum y-
coordinate of a vertex in the piece of 0V corresponding to the parent of the family. In
vL
LOWER
FIG. 10. Assembling subregions. The family tree nodes associated with several regions are shown.
Trapezoids labeled "0" are ignored completely.
the latter case, the piece of OV corresponding to the parent consists of a single piece of
a boundary segment of V. We split this piece at the vertex with maximum y-
coordinate to form two pieces, which become the side boundary segments of the subre-
gion; the top of the subregion is empty. The definitions are symmetric for subregions
below L.
Let us restate the difference between the algorithm above and the one outlined in
Section 1. In the former, a maximal deep section is treated as if it had only two inter-
sections with L (the essential ones), until it is discovered that some intersection not in
the section is enclosed by these two. This approximation to the truth works because
the intersections in the section occur in the same order along the section as they do
along L (or in reverse order). If no "foreign" intersections intervened, the algorithm of
Section 1 would merely chop the section between each pair of contiguous boundary
segments in Step 2 and put them back together in exactly the same order in Step 4.
The new algorithm avoids this unnecessary work.
We now want to quantify the work saved by the new algorithm. Our main result
is that the total number of visible pairs reported during the processing of an n-vertex
polygon is O (n). This implies that the time spent doing Jordan sorting, not including
calls of refine, is O (n).
LEMMA 3. The processing of an n-vertex polygon requires at most n-2 invoca-
tions of Steps 2-4.
Proof. Each vertex except the ones of maximum and minimum y-coordinate can
be selected as v in Step at most once. []
LEMMA 4. Consider a single invocation of Step 3. Let k be the number of visi-
ble pairs reported during this invocation that were not reported during previous invo-
cations. The total number of intersections sorted during this invocation, including
those introduced by refinement, is 0 (k + 1).
Proof. First we count the essential intersections. We call an essential intersec-
tion x good if x is a vertex (i.e. x---v) or if the two vertices preceding and following x
along 0V, say v’ and v", are in the same part of tgV (top, bottom, left, or right) and
not strictly on the same side of L. Otherwise x is bad. We claim that if x is a good
intersection other than v, then the edge that contains x belongs to a newly reported
visible pair. This is true if the part of 0V from v’ to v" consists of the line segment
joining v’ and v", since the visible pair containing the edge from v’ to v" that will be
reported is the first one reported containing that edge. It is also true if the part of
from v’ to v" consists of a partial edge from v’ to the line y ---Ymax (or y Y min), a
segment of the line y Y max (or y Y min, respectively), and a partial edge from the
line y ---Ymax (or y Y min, respectively) to v". To see this, suppose without loss of
generality that v’ is strictly below L and OV contains a partial edge from v’ to the line
Y --)’max. (See Figure 11.) Intersection x is on this partial edge. Along the line L,
the edge from v’ sees something other than the edge into v", and thus will be con-
tained in a newly reported visible pair, since if two edges see each other horizontally,
the part of each edge that sees the other is connected. Thus in either case the claim is
true. The claim implies that the number of good intersections is O (k + 1).
Consider the bad intersections. Any mixed boundary segment contains at most
two bad intersections (the first and last in the segment) and, if it is a top or bottom
segment, at least one good intersection. Any maximal deep section contains at most
two bad intersections (the first and last in the section). Such a section either (i) is
followed by a shallow segment, (ii) is followed by a mixed top or bottom boundary
segment, or (iii) contains the last segment on its side. In case (i) the last intersection
is good. The number of bad intersections in case (ii) is O (k + 1), since the mixed seg-
ment contains at least one good intersection. At most four bad intersections (the last
two within each of the top and bottom boundaries) can fall into case (iii). There are
also at most two bad intersections within each of the left and right sides. Thus the
number of bad intersections is O (k + 1).
It remains for us to count the nonessential intersections introduced by refinement.
Suppose that a call refine ({Xi_l,Xi} X) returns a pair x’,x". Both of the edges that
contain x’ and x" will be contained in newly reported visible pairs, since along L they
FIG. 11. The edge that contains x belongs to a newly reported visible pair.
see something other than each other. Thus the number of intersections introduced by
refinement is O (k). rn
The following theorem summarizes our analysis of the algorithm so far.
THEOREM 1. Irl processing an n-vertex polygon, the visibility algorithm reports
0 (n) risible pairs and spends 0 (n) time in Jordan sorting, not including its calls to
refine. This includes all processing of subregions.
Proof Immediate from Lemmas 1, 3 and 4. Ixl
4. Use of balanced divide and conquer. The visibility algorithm of Section 3 can
in the worst case generate regions containing a total of 1 (n 2) boundary segments
(counting a boundary segment each time it occurs in a region). As we shall see in
Section 5, obtaining an O (n log log n)-time implementation of the algorithm requires
reducing the total number of boundary segments to O(nlogn). We do this by
refining the algorithm so that it uses a balanced divide-and-conquer strategy. The
refinement consists of choosing the vertex v carefully in Step 1. Roughly speaking, we
want to slice a region with many boundary segments so that at most a proper fraction
of the segments end up in any one of the subregions. A choice that works and that
can be made quickly is the following:
Choose splitting vertex. Let region V have top boundary segments and b bot-
tom boundary segments. Suppose >/ b. (Otherwise, proceed symmetrically.) If
< 2, choose any vertex v whose y-coordinate is not in {Y min ,Y max} Otherwise, divide
the list of top boundary segments into three sublists, with the first and last containing
[t/3J segments and the middle one the remainder. Among the segments in the middle
sublist, choose as v the vertex whose y-coordinate is minimum.
We call the visibility algorithm refined to use this selection strategy the balanced
division algorithm; we call the algorithm with an arbitrary selection strategy the gen-
eric algorithm. In the analysis to follow, we regard two boundary segments as distinct
only if their vertex sets or their end edges (if there are any end edges) are different.
LEMMA 5. In processing an n-vertex polygon, the generic visibility algorithm
creates 0 (n) distinct boundary segments altogether.
Proof The only way the algorithm can create new boundary segments is by split-
ting an old boundary segment in two, at an intersection point that is input to the Jor-
dan sorting algorithm or at the vertex of maximum or minimum y-coordinate in a
subregion. By Theorem there are O (n) such splitting points. Hence there are O (n)
distinct boundary segments, rn
LEMMA 6. Let V be a region that has s boundary segments. If V is sliced using
balanced division, then no subregion contains more than 7sl8 of the original boun-
dary segments of V.
Proof Let V contain top boundary segments and b bottom boundary segments.
We have s b + + 2. Suppose without loss of generality that >/ b. If < 2 the
lemma is immediate, since some boundary segment is cut into new boundary segments
distinct from the original; thus the original appears in no subregion. Suppose >/ 3.
Consider where the top boundary segments of V end up after slicing. A segment that
is mixed with respect to the slicing line L is cut into new boundary segments distinct
from the original; thus the original appears in no subregion. There are at most 2 [t/3J
deep top boundary segments, which implies that each subregion below L contains at
most b + 2tl3 + 2 < 7sl8 of the boundary segments of V. A deep top segment can-
not end up in a subregion above L; only a part of it, constituting a distinct boundary
segment, can. Thus among the top segments, only the shallow ones can end up in
regions above L. A set of shallow segments can end up in the same subregion only if
it forms a shallow section. By the choice of L, any such shallow section can contain at
most [t/3J < 2tl3 top boundary segments of V. Thus any subregion above L
contains at most b + 2tl3 + 2 <
7sl8 of the boundary segments of V. rn
THEOREM 2. When the balanced division algorithm processes an n-vertex
polygon, the sum over all regions of the number of boundary segments per region is
O (n log n).
Proof. One way to prove this theorem is to write down a recurrence based on
Lemma 6 and solve it. Instead, we shall use an amortization argument based on a
credit analysis (see [26]). When the balanced division algorithm creates a distinct
new boundary segment, we assign 15 log16/15 n credits to the segment. Each subse-
quent time that the segment appears in a subregion, we remove a credit. We shall
show that the number of credits always remains nonnegative, which implies by
Lemma 5 that the sum over all regions of the number of boundary segments is
O (n log n).
To show that the number of credits remains nonnegative, we actually prove the
following stronger credit invariant: a region that has s boundary segments has at least
s 1og16/5 s credits. The invariant is certainly true initially. Suppose it is true before
some invocation of Steps 1-4. Let V be the region to be subdivided, and let s be its
number of boundary segments. Before the subdivision, V has at least s lOgl6/ss
credits, of which we allocate log6/ss to each boundary segment. One of these pays
for the appearance of the segment in V, leaving (1og16/15 s)-I log16/5(15s/16) as its
contribution to the credits of the subregion in which it appears. Consider a subregion
V’ formed by splitting V. Suppose its boundary contains p of the boundary segments
of V and q newly created boundary segments; let s’--p/q. To verify that V’ has
s’ logl6/15s’ credits, there are two cases to consider. If q > s’/15, then the total
number of credits is at least the number of credits assigned to new segments:
15q 1og16/15 n s’ lOgl6/15 s’.
s’ log16/15 n
If q <s’/15, then since p < 7s/8 by Lemma 6, we have s’ < 15s/16. The total
number of credits is
p log6/5(15s/16) + 15q 1Ogl6/15 n p lOgl6/15 (15s/16) + 15q log16/15 (15s/16)
> s’ Iog6/15 (15s/16) > s’ 1og6/ 5 s’.
By induction on the number of steps, the credit invariant is always true, from which
the theorem follows.
5. Representation of the boundary using finger search trees. We have now almost
completed our presentation of the visibility algorithm. The task that remains is to
choose a data structure for the lists that represent the boundary segments and boun-
dary groups, and to analyze the effects of this choice. To represent both kinds of lists
we use heterogeneous finger search trees (see the appendix). As we shall see, this
gives an overall O(n log logn) running time for the balanced division visibility algo-
rithm.
We represent each boundary segment by a heterogeneous finger search tree in
which each leaf contains a vertex in the segment. Left-to-right order in the tree
corresponds to the order of the vertices along the segment. In addition, if the segment
has one or two end edges, we store these edges with the tree. Within the tree, we
maintain two heap orders, both with respect to the y-coordinates of the vertices. One
is by increasing y-coordinate, the other is by decreasing y-coordinate. That is, each
node in the tree contains the maximum and minimum y-coordinates of all leaves
reachable from it in the tree. (See Figure 12.) This allows us, for any given value of
y, to find the leftmost (or rightmost) vertex with y-coordinate less than (or greater
B D
5
E
a
2
FIG. 12. A boundary segment and its representation as a heterogeneous finger search tree. (The
drawing conventions are explained in Figure 22.)
than) the given value, in O(1 +log(min{d, s-d} + 1)) time, where s is the total
number of vertices stored in the tree and the one found is the dth. We can also find
the vertex of maximum (or minimum) y-coordinate in the same time. The amortized
time to split the tree at the dth out of s vertices is also O (1 + log(min{d, s-d} + 1)).
We represent each list of top boundary segments or bottom boundary segments
constituting the top or bottom boundary of a region by a heterogeneous finger search
tree in which each leaf represents a boundary segment. Left-to-right order in the tree
corresponds to the order of the boundary segments clockwise around the boundary.
Each leaf contains a pointer to the tree representing the corresponding boundary seg-
ment, as well as the end vertices or edges of the segment, and the maximum and
minimum y-coordinates of the vertices within the segment. We think of each node in
the tree as representing the section (sublist of boundary segments) corresponding to
the set of leaves reachable from the node. We store in each node the first and last end
vertices or edges of the corresponding section, the number of segments in the section,
and the maximum and minimum y-coordinates of vertices in the section. (See Figure
13.) All these values can be updated bottom-up in the interior of the tree and top-
down along the left and right paths.
9
8
7
6
5
4
FIG. 13. A group of boundary segments and its representation as a heterogeneous finger search tree.
(The drawing conventions are explained in Figure 22; capital letters represent end edges.)
All of the following operations can be performed in O(1 +log(min{d, s-d} + 1))
time, where the segment found is the dth out of s:
(i) Find the leftmost (or rightmost) segment in the tree that contains a vertex
with y-coordinate less than (or greater than) a given value;
(ii) Find the dth segment;
(iii) Suppose all the segment vertices lie strictly above (or strictly below) a given
horizontal line L, and that all end edges of the segments cross L. Given a value x,
find the leftmost (or rightmost) segment in the tree having an edge whose intersection
with L has x coordinate less than (or greater than) x. (All four possibilities, leftmost
less than, leftmost greater than, etc., are allowed.)
In addition, inserting a new segment next to the dth out of s or splitting at the
dth segment out of s takes O (1 + log(min{d, s-d} + 1)) amortized time. Concatenat-
ing two trees takes O (1) amortized time.
Let us examine the manipulations of the boundary data structures required to

carry out the steps of the balanced division visibility algorithm. We describe these
step by step, including a timing estimate for some of the computations.
Step 1. Given V, determine the number of top and bottom boundary segments in
its boundary, say and b, respectively (O(1) time). Assume > b. (The other case
is symmetric.) If < 2, choose a segment of the boundary that contains some vertex
with y-coordinate strictly between Y min and Y max, and select as v the first such vertex
in the segment (O (1) time). If >/ 3, find the minimum y-coordinate of the vertices
in the middle third of the top boundary segments (time to be analyzed below). This
defines the slicing line L.
Step 2. Split the tree representing the top boundary between each pair of seg-
ments that differ in type among the types shallow, deep, and mixed (time to be
analyzed below). This splits the top boundary list into mixed segments and maximal
deep and shallow sections. Repeat this for the tree representing the bottom boundary
(time to be analyzed below). For each mixed segment, split its tree between each pair
of consecutive vertices, one on each side of L (time to be analyzed below). Split the
tree that contains the vertex lying on L at that vertex, putting the vertex in both of the
resulting trees (time to be analyzed below). Each of the splits performed corresponds
to an essential intersection of the boundary with L. Form a list of these intersections,
in the order in which they occur along the boundary, by examining the list of trees
representing the deep sections and the new boundary segments that have been formed
by splitting mixed segments (O (1) time per essential intersection).
Step 3. To execute a call refine ({xi-,xi}, x), examine the tree representing the
deep section whose first and last intersections with L are xi- and xi. Assume
xi- < xi. (The other case is symmetric.) Find in this tree the rightmost segment
whose first intersection with L is less than x (time to be analyzed below). If the last
intersection of this segment with L is greater than x, return no pair (O(1) time).
Otherwise, split the section between this segment and the next one, and return as x’
and x" the last intersection of this segment and the first intersection of the next one
(time to be analyzed below).
Step 4. For each pair in the upper tree whose depth is odd and greater than one,
split the tree representing the corresponding boundary segment at its vertex of max-
imum y-coordinate (time to be analyzed below). Put the splitting vertex in both of
the resulting trees. Proceed symmetrically for the boundary segments corresponding
to pairs in the lower tree. For each family in both trees, concatenate the boundary
segments and deep sections corresponding to the pairs in the family to form the boun-
dary of the subregion corresponding to the family (O(1) time per pair). Because the
input polygon is simple, the order in which polygon vertices appear on the boundary of
the subregion is consistent with their order in the original polygon. (See Figure 14.)
This means that the concatenation will never need to reverse the order of boundary
segments.
Now let us analyze the running time of this implementation of the balanced divi-
sion algorithm. Observe that for each segment found within a top or bottom boun-
dary, and for each vertex found within a segment, a split occurs at that segment or
vertex. Since the timing estimates for finding and splitting are the same, the time
spent splitting dominates the time spent finding such segments and vertices, including
the time to find the y-coordinates of the splitting vertices in Step 1. Thus, by the tim-
ing estimates above and Theorem 1, the total running time of the algorithm is O(n)
plus at most a constant times the time for tree insertions, splits, and concatenations.
It remains to estimate the time for tree update operations. Every insertion is at
one end of a finger search tree and thus takes O (1) amortized time. The updates on
FIG. 14. A subregion that would cause trouble for Step 4. The arrows indicate the direction of the
two boundary segments in the original polygon. Such subregions cannot occur for simple polygons.
the trees representing segments are only splits and insertions, of which there are O (n).
The total running time of these updates obeys a recurrence that is essentially the same
as (1) (Section 1) and is thus O (n).
The updates on the trees representing top and bottom boundaries include concate-
nations, and recurrence (1) does not apply. To analyze these operations, we first
observe that the amortized time per concatenation or insertion is O (1). Since the
total number of such operations is O (n), their total time is O (n).
To analyze the O(n) splits, consider a particular visibility region Vi that has a
total of si boundary segments. The total time to split the two trees representing the
top and bottom boundaries is O(ki + .-.ki+l 2j-o log si,j), where k; is the total number of
splits and Si, O,Si, ,Si, ki+l are the numbers of segments in each of the trees that
are created by the splits. (Starting from two trees, k splits produce k + 2 trees; if
there is only one tree initially, we take Si, ki+l 1.) We have si,j >/ for all j, and
j-o si,j <si+l. Since the logarithm is a concave function, the estimate of splitting
time is maximized when all the pieces are of equal size, giving a bound of
O(ki + (ki+2) log ((si+l)/(ki+2))).
We evaluate the total time to perform all O (n) splits,
O(Zi (ki + (ki+2) log ((si+l)/(ki+2)))), in two parts. Call Vi a good region if
t si/(lg n)2, and bad otherwise. By Theorem 2, ,isi O(n logn), so the total
namber of splits that occur while processing good regions, ,ki<si/(logn)Eki, is
(tllog n); using O (log n) as a generous time bound for these splits, the total time to
l|it good regions is O (n). It remains to bound the time to split bad regions:
O[ (k+(k+2)log((si+l)/(ki+2)))]
ki>si/(logn)
---0[ (kiW(ki+2)loglogn)]--O(nloglogn),
ki > si /(log n)
since Zi ki 0 (n).
We conclude that the total running time of the visibility algorithm with balanced
division is O (n log log n).
6. Remarks, applications and open problems. We have presented an
O (n log log n ) -time algorithm for computing horizontally visible edge-vertex pairs
inside a simple polygon. By the linear-time reduction of triangulation to the visibility

problem [5|,[9] we obtain an O(n log logn)-time triangulation algorithm. The main
ingredients of our algorithm are Jordan sorting, balanced divide and conquer, and
finger search trees. It is intriguing to note that both the Jordan sorting algorithm and
the visibility algorithm use finger search trees, but of two different kinds. The Jordan
sorting algorithm requires fast access in the vicinity of any position in the tree but
does not need to search on a secondary heap order. Homogeneous finger search trees
satisfy these requirements. The visibility algorithm itself does need to search on
secondary heap orders, but requires fast access only in the vicinity of the first and last
positions. Heterogeneous finger search trees satisfy these requirements. Our algo-
rithm exploits to the fullest the properties of these structures.
Finger search trees are sufficiently complicated that one would probably not want
to use them in an actual implementation. The dynamic optimality conjecture of Slea-
tor and Tarjan [23] suggests that the O (n log logn) time bound is still valid if splay
trees (a form of self-adjusting search tree) are used in place of finger search trees.
The use of splay trees might lead to a practical implementation of our algorithm,
although this must be verified by experiment. Other minor changes in the algorithm
might be useful in practice. We leave this as a topic for future research.
Our visibility algorithm can be modified to accommodate vertices having the same
y-coordinate. To handle the resulting tangent intersection points in the Jordan sorting
step (Section 2), we represent such a point xi by a dummy pair (xi,xi) which we add
to the lower tree if the tangency is on the top side of the splitting line L, or to the
upper tree otherwise. The remaining changes to the algorithm are straightforward.
(See e.g. 30].)
An efficient triangulation algorithm has a number of applications in computa-
tional geometry. These applications typically involve one (or possibly a few) triangu-
lations and some linear-time pre- and postprocessing. Our triangulation algorithm
gives O(n log logn)-time algorithms for these applications. Any improvement in the
time to triangulate would give corresponding improvements in the applications. Such
applications include:
(i) several polygon decomposition problems [9] (where minimality, as in [17], is
not required);
(ii) regularizing (or triangulating) a planar subdivision that is given as a con-
nected planar graph [8];
(iii) computing the internal distance between two points in a polygon, and finding
the point visibility polygon for a point inside the polygon [3];
(iv) solving the single source shortest path problem inside a polygon, and comput-
ing internal visibility information from an edge inside a polygon [11 ];
(v) testing two polygons for intersection, and decomposing simple splinegons [24]
into a union of differences of unions of convex sets [7];
(vi) determining translation separability of two simple polygons [1 ];
(vii) finding a shortest watchman route in a simple rectilinear polygon ([6, Thm.
31).
An important application of our visibility algorithm is to test whether an n-vertex
polygon P is simple, and to exhibit a self-intersection of OP if it is not simple. We
shall show how to modify our algorithm to perform these tasks in O (n log log n) time.
Even though the error-correcting Jordan sorting algorithm detects some instances
of nonsimplicity as uncorrectable crossings or violations of the nonenclosure property,
the successful completion of the visibility algorithm is not proof against nonsimplicity
of the input polygon. Among the problems with which a guaranteed simplicity test
(a)
v4
vz
v:
Vo
(b)
V2 V7
(c) Vo
FIG. 15. Nonsimple polygons that cause no trouble in the algorithm for computing visibility informa-
tion. In (c), a slice through v separates the polygon into three simple pieces.
must cope are polygons that are self-tangent at a vertex (Figure 15a), polygons for
which an interior cannot be defined by any consistent labeling of the edges (Figure
15b), and nonsimple polygons that can be sliced into simple pieces (Figure 15c).
Our algorithm for testing simplicity is as follows. First we check that no two
consecutive edges of P intersect in more than their common endpoint. Next, we run
the visibility algorithm on the polygon P and on its "inside-out" partner Q, defined as
in the proof of Lemma 2. We abort the algorithm and declare that P is nonsimple if
one of the following cases occurs:
(i) the Jordan sorting step finds an intersection point common to two parts of P
other than an endpoint of two consecutive edges (see Figure 15a);
(ii) the Jordan sorting step detects an uncorrectable crossing or violation of the
nonenclosure property;
FI. 16. The ordering of the four corners of this visibility region implies that it is not simple.
(iii) a subregion is constructed in Step 4 whose side boundary segments, say S

and $2, are known to cross, because the intersections of S and $2 with the top
bounding line are in the opposite order from the order of their intersections with the
bottom bounding line (see Figure 16).
If the visibility algorithm runs to completion on both P and Q, we declare that P
is simple.
In our discussion of Step 4 in Section 4, we noted that if the polygon is simple,
then the order of vertices along the boundary segments is consistent with the order of
the boundary of the subregion being reassembled. It is conceivable if the polygon is
not simple that Step 4 could be presented with a subregion whose boundary segments
appear in an anomalous order, as in Figure 14. Fortunately, this situation cannot in
fact occur: the existence of such a nested pair implies by the Jordan curve theorem
that the current region being processed has a nonsimple boundary, and indeed that the
segments of the boundary defined by the slicing line do not have the noncrossing pro-
perty. Therefore, the nonsimplicity will be detected in Step 3.
THEOREM 3. The simplicity-testing algorithm is correct.
Proof Certainly if the simplicity-testing algorithm declares that P is not simple
then 0P has a self-intersection. Suppose the algorithm reports that P is simple. The
visibility computations in the algorithm produce two sets of regions. Let P and Q be
the sets of regions produced when the visibility algorithm runs on P and Q, respec-
tively; each region in P and Q is either a trapezoid or a triangle. Some of the regions
in Q are bounded by one or more edges of Q-P, i.e., by edges that were added to
invert polygon P. Let Q’ be the set of regions formed by taking each region in Q and
extending it to infinity in the direction of any edge in Q-P. Regions in Q’ can be tra-
pezoids, triangles, halfplanes, or infinite regions bounded by two horizontal lines and
part of a side of P.
It is tempting to say that the regions in P partition the "interior" of P, but we
cannot say this, because we do not yet know that P has an interior. However, because
of the way in which the regions in P were produced, we know that they can be glued
together along shared horizontal visibility edges to form a region that is topologically
equivalent to a disk. This is necessary but not sufficient for P to be simple (consider
the polygon in Figure 15c). The visibility algorithm could be modified easily to pro-
duce this "gluing," or, more properly, its dual graph, in which regions are vertices,
and regions that share a horizontal visibility edge are joined by an edge in the dual
graph.
Since the visibility algorithm succeeded, we also know that the regions in Q can
be glued together along horizontal visibility edges to form a region that is topologically
equivalent to the disk. This gluing can be extended naturally to Q’, which is topologi-
cally equivalent to the punctured plane. In what follows, we use the regions in P and
Q’ to construct a mapping from the plane onto itself.
Let C be a circle in the plane, and choose n distinct points on C corresponding to
the vertices of P; this induces a natural correspondence between points of 0P and
points of C. For each vertex-edge or edge-edge visible pair in P reported by the visi-
bility algorithm, connect corresponding points on C by a path through the interior of
C; make all these paths disjoint except for corresponding endpoints. (The dual graph
of the regions in P provides a natural way to do this constructively. Processing a ver-
tex of degree one in the dual requires that we draw a path between two points on C;
that path divides the disk into two parts, one of which can be discarded and never
enters into further computation of the mapping. Thus we can perform the complete
construction by processing and deleting vertices of degree one from the dual until the
dual is empty.) These paths divide the interior of C into regions corresponding to the
regions of P. Similarly, for each piece of visibility information in Q’, construct a
corresponding path joining two points of C and passing through the exterior of C. If
the piece of information represents a vertex or edge that sees arbitrarily far to the left
or right, the corresponding path leads from C to infinity. Make all the paths on the
exterior of C noncrossing. This partitions the exterior of C into regions corresponding
to the regions of Q’. (See Figure 17.)
We can construct a continuous mapping h of the plane onto itself that takes each
region of the interior of C onto the corresponding region of P and each region of the
exterior of C onto the corresponding region of Q’. The mapping is onto because every
point in the plane is in some region of P or Q’: For any point x, move horizontally
right from x until hitting OP. If the right side of 0P is hit (with respect to clockwise
order around igP), x is in some region of P. Otherwise x is in some region of Q’. If
0P is not hit, x is in some region of Q’.
Because P and Q’ are finite and the preimages of distinct regions have disjoint
interiors, the mapping h is a covering map from the plane onto itself: any point x in
the plane has an open neighborhood N such that h -1 (N) is the disjoint union of a
finite number of open sets [21]. Moreover, since the domain of h is connected, every
point in its range is the image under h of the same number of points of its domain
[21, ex. 8-3.5, p. 336]. Since any point in the open half plane that lies above the hor-
izontal line through the highest vertex of P is the image under h of only one point, h is
1-1. Thus h is a homeomorphism of the plane onto itself. This proves that OP is
homeomorphic to C, so P is simple, rn
If the simplicity-testing algorithm reports that P is not simple, we can produce a
witness to its nonsimplicity in O (n) additional time. If the nonsimplicity is detected
in Case (i), the self-intersection is available immediately. Otherwise (if Case (ii) or
(iii) occurs) we can find one or two bounding lines and two boundary segments S
and $2 with ends on the bounding lines such that the two boundary segments are
guaranteed to cross. There are seven possible configurations of the two boundary seg-
V3
FIG. 17. Illustrating the mapping h constructed in the proof of Theorem 3. For 0 < < 5,
h (u i) vi. Dashed paths in the upper figure correspond to vertex-edge visibility segments in the lower
figure. Arrowheads indicate paths to infinity.
ments, illustrated in Figures 18 and 15b. We apply the following three steps repeat-
edly until an explicit crossing is found:
Step 1. Choose a vertex on S U $2 not having maximum or minimum y-
coordinate. Let L be the horizontal line through this vertex.
Step 2. Find all intersections of S and $2 with L, in the order in which they
occur along S1 followed by $2.
Step 3. Jordan sort the intersections. The Jordan sorting step must either find
an explicit self-intersection or a violation of the noncrossing property. If such a viola-
tion is found, let S’ and S[ be the crossing subsegments. Replace S and $2 by S’
and S[. If S’I and S[ are both single partial edges, report their intersection.
(a)
(b) (e)
(c) (f)
FIG. 18. Possible configurations of crossing boundary segments: (a) four points on one bounding line;
(b) three points on one bounding line and one on the other; (c) two points on each bounding line; (d), (e),
and (f) are degenerate cases of (a), (b), and (c), respectively. Figure 15b depicts a degenerate case of (f).
Degenerate cases can be detected by examining the interior angle at the point or points of degeneracy.
An analysis like that in Sections 3-5 shows that this postprocessing takes O (n)
time if the segments are represented by finger search trees. (Concatenation of finger
search trees and balanced division are not needed.)
The algorithms for testing simplicity and producing a witness to nonsimplicity are
easily extended to work on connected polygonal paths that are not closed. The first
step of the extension is to draw a line through the two endpoints of the path, thus
chopping the path into boundary segments that lie entirely on one side of the line, and
to Jordan sort the points of intersection between the path and the line. If the Jordan
sorting detects a violation of the noncrossing property, the algorithm for finding a
crossing can be applied directly to the two boundary segments involved. Otherwise we
use processing akin to that in Step 4, augmented to cope with boundary reversals as in
Figure 14, to construct polygons that lie entirely on one side of the line; the path is
simple if and only if each of those polygons is simple.
The algorithms for computing horizontal visibility information, for testing simpli-
city, and for producing a witness to nonsimplicity, can be extended to work on curves
that obey certain mild restrictions. (See e.g. [22],[24].) To prepare the curve for pro-
cessing add vertices to each edge to form a curve each of whose edges is monotone in
the y-direction. The algorithms can now be run directly (given suitable procedures for
computing the intersection of a curved edge and a line), because the edges of the
object have the property that if a collection of edges crosses two horizontal lines then
the edges cross both lines in the same order. The other extension occurs in simplicity
testing: we must check that the left and right sides of each trivial visibility region do
not cross. If all of the output regions have this property, then the curve is simple; oth-
erwise we have an immediate witness to its nonsimplicity. Both the preparation of the
curves and the postprocessing of the output regions can be performed in O (n) time.
Several open problems remain. First and foremost, of course, is determining
whether there is a linear-time triangulation algorithm, or even a o (n log logn)-time
algorithm. Resolving this question seems to require a new idea. One possible
approach is to invent a data structure for representing a polygonal curve that will
allow fast computation of its intersections with an arbitrary horizontal line segment, or
even with an arbitrary horizontal half line. Perhaps such a data structure can be built
using information computed by the visibility algorithm called recursively on small
pieces of the boundary, say of size O(logn). The result might be a visibility algo-
rithm running in O (n log" n) time. Another open problem is to determine how fast all
the self-intersections of a polygonal curve can be computed: can bounds better than
those for an arbitrary collection of line segments [4] be obtained?
Appendix. Finger search trees. A finger search tree is a type of balanced search
tree in which access in the vicinity of certain preferred positions, indicated by fingers,
is especially efficient. Finger search trees were introduced by Guibas, McCreight,
Plass and Roberts [12] and further developed by many other researchers
[2],[15],[18],[28],[29]. We shall discuss two kinds of finger search trees with slightly
different properties, heterogeneous trees and homogeneous trees. We base our
development on a particular kind of balanced tree, the red-black tree [20],[25],
although other kinds of balanced trees, such as a,b-trees [16],[19], form a suitable
basis as well. We are mainly interested in amortized, not worst-case, complexity
bounds.
For our purposes a binary search tree is a full binary tree in which each external
node contains a distinct item selected from a totally ordered universe, with the left-to-
right order of external nodes consistent with the total order on the items. Each inter-
nal node contains a key, which is an item greater than or equal to all items in its left
subtree and less than all items in its right subtree. We can use the keys to search for
the largest item in the tree less than or equal to a given one, by starting from the root
and going to the left child if the item in the current node is greater than or equal to
the given one, going to the right child otherwise, and repeating until an external node
is reached. The desired item is either the one in the external node reached or the one
in the preceding external node, which can be found by backing up the search path to a
right child, starting from its left sibling, and going through right children to an exter-
nal node. The time to search for an item is proportional to the tree depth.
A red-black tree is a binary search tree in which each node has one of two colors,
red or black. The node colors obey the following constraints (see Figure 19):
(i) all external nodes are black;
(ii) all paths from the root to an external node contain the same number of black
nodes;
(iii) any red node, if it has a parent, has a black parent.
The depth of a red-black tree containing n items is O(logn). To insert a new
item into a red-black tree, we search for the greatest item less than it in the tree.
When the search reaches an external node, we replace this node by an internal node
having two children, the old external node and a new external node containing the new
FIG. 19. A red-black tree; solid nodes are black; hollow nodes are red. (Only the colors of the nodes
are shown.)
item. The new internal node contains as its key the smaller of the two items in its
children. The new internal node is colored red. This may violate the red constraint
(iii). To restore the red constraint, we proceed bottom-up along the search path,
applying the recoloring transformation in Figure 20a until it no longer applies, fol-
lowed by one application of Figure 20b, c, or d if necessary.
A deletion is similar. To delete an item, we find the external node containing it.
We replace the parent of this node by the sibling of the node to be deleted. This may
violate the black constraint (ii), producing a node that is short: all paths down from it
to external nodes contain one fewer black node than paths down from its sibling. To
restore the black constraint, we proceed bottom-up, applying the recoloring transfor-
mation of Figure 21a until it no longer applies, followed by one application of Figure
21 b if necessary, and then possibly one application of Figure 2 a, c, d, or e.
The worst-case insertion or deletion time in an n-item red-black tree is O (log n),
but the amortized insertion/deletion time is only O(1), not counting the time to
search for the node at which the insertion or deletion takes place. (This is a restate-
ment of a result of Huddleston and Mehlhorn [16] and Maier and Salveter [19] con-
cerning a,b-trees.) To prove this, we define the potential of a red-black tree to be the
number of black nodes with two black children plus twice the number of black nodes
with two red children. We define the actual time of an insertion or deletion to be one
plus the number of local transformations applied and the amortized time to be the
actual time plus the net increase in potential caused by the operation. With these
definitions, if we start with an empty tree, the total actual time for a sequence of
insertions and deletions is at most the sum of the amortized times, since the initial
potential is zero and the potential is always nonnegative. Furthermore the amortized
time of an insertion or deletion is O (1), since any of the transformations in Figures 20
and 21 increases the potential by O (1) and the nonterminal transformations 20a and
21a both decrease the potential by at least one.
(a)
OR
FIG. 20. The rebalancing transformations in red-black tree insertion. Symmetric cases are omitted.
All unknown children of red nodes are black. In cases (c) and (d) the bottommost black node shown can
be external.
In an ordinary binary search tree, each node points to its two children. We con-
vert such a tree into a heterogeneous finger search tree by making each node along
the left path 2 point to its parent instead of its left child, and each node along the right
path point to its parent instead of its right child. Access to the tree is by two fingers
pointing to the leftmost and rightmost external nodes. (See Figure 22.)
In an n-item heterogeneous search tree, we can search for an item d positions
away from either end in O(1 +log(min{d,n-d} + 1)) time, by searching up along the
left and right paths concurrently until we find a subtree or two subtrees guaranteed to
contain the desired item, and then searching down in this subtree or subtrees. Furth-
ermore we can insert or delete an item d positions from either end in
O(1 +log(min{d,n-d} + 1)) amortized time. We can also search for an item based
on its position or based on a secondary heap order. To accommodate search by posi-
tion, we store in each internal node the number of external nodes reachable from it
(by paths of pointers). To accommodate search based on a secondary heap order, we
assume each item has an associated secondary value. We store in each internal node
the minimum and maximum values of items reachable by paths of pointers. (See Fig-
ure 22.) By searching up along the left and right paths concurrently and then down
into an appropriate subtree or subtrees, we can perform the following kinds of
searches in O (1 + log(min{d,n-d} + 1)) time:
(i) Find the dth item in the tree;
2The left path in a binary tree is the path from the root through left children to an external node. The
right path is defined symmetrically.
1’74 R. E. TARJAN AND C. J. VAN WYK
(o)
FIG. 21. The rebalancing transformations in red-black tree deletion. The two ambiguous (half-solid)
nodes in (d) have the same color, as do the two in (e). Minus signs denote short nodes. In (a), the top
node after the transformation is short unless it is the root.
(ii) Find the leftmost (or rightmost) item whose secondary value is at least (or at
most) a given value, if the item found is the dth.
The auxiliary position and secondary value information must be updated when
insertions and deletions are performed. This updating can be done bottom-up along
the search path, i.e. bottom-up within the tree and top-down along the left or right
path. The amortized time to insert or delete the dth item, including the search time,
is O (1 + log(min{d,n-d] + 1)).
We now wish to extend our repertoire of update operations to include concatena-
tion and splitting of trees. We shall discuss only the effect of these operations on the
tree structure; it is easy to verify that the pointers, keys, and auxiliary position and
secondary value information can be updated in the claimed time bounds. We define
the rank of a node in a red-black tree to be the number of black internal nodes on any
path from the node down to an external node; the rank of an external node is zero.
We can compute the rank of a node in time proportional to the rank by walking down
through the tree.
Concatenation is the simpler operation to describe. Suppose we wish to combine
two trees T1 and T2 into a single tree; we assume that all items in T1 are less than
all items in T2. Let xl with rank rl and x2 with rank r2 be the roots of T1 and T2,
respectively. Assume r < r2. (The other case is symmetric.) To concatenate T1
FIG. 22. A heterogeneous red-black finger search tree. The colors of nodes are not shown. The items
are the letters a through f. The numbers in external nodes are secondary values. The numbers in internal
nodes are the minimum and maximum secondary values reachable from the nodes. The numbers outside
the nodes are the number of external nodes reachable from them.
and T2, we walk up the left path of T 2 until we reach a node, say y, with rank equal
to r 1. We replace y in T2 by a new red node whose left child is X and whose right
child is y, correcting any violation of the red constraint as in the case of an insertion.
The amortized time for the concatenation is O(1 +min{rl,r2}). If we change the
definition of potential so that the potential of a tree is the rank of its root plus the
number of black nodes with no black children, then the amortized time of a concate-
nation is O(1); the amortized time for inserting or deleting the dth item out of n
remains O (1 + log(min{d,n-d} + 1)).
Suppose we wish to split a tree T containing n items at the dth item, dividing it
into a tree T1 containing the first d items and a tree T2 containing the last n-d
items. First we locate the dth item. Then we walk up along the search path to the
left or right path, deleting every node along the search path except the external node
containing the dth item, Assume we reach a node x on the left path. We concatenate
the trees to the left of the search path (including the one consisting of the single node
containing the dth item) in right-to-left order to form T1. We concatenate the trees
to the right of the search path whose roots are descendants of x to form a tree T. If
node x has no parent, then tree T is the desired T2. Otherwise, there remains
another tree T’ containing the parent of x, say y. Tree T’
is missing a node, since
node x was deleted. We replace node y by its right child, and repair the possible
resulting shortness as in a deletion. Then we concatenate T and T’ to form T2. A
careful analysis (see e.g. [20, pp. 214-216]) shows that the amortized time for split-
ting is O(1 +log(min{d,n-d} + 1)) for either the new or the old definition of poten-
tial.
a, 4,4 d, 3,6 2
C, 3,6 2. e, 2,6 3
FIG. 23. The pointers in a homogeneous red-black finger search tree.
Heterogeneous finger search trees are used in the visibility algorithm to represent
parts of region boundaries. The term "heterogeneous" refers to the fact that the
pointer structure favors certain specific access positions, namely the two ends. In con-
trast, homogeneous finger search trees support fast access in the vicinity of any item.
We make a red-black tree into a homogeneous finger search tree by adding additional
pointers to it; namely, we make each node point to its two children and to its parent.
Each black node also points to its left and right neighbors, the black nodes of the
same rank that precede and follow the given node in symmetric order. (See Figure
23.) These extra pointers are called level links.
The level links support searching for a given item starting from an arbitrary item
in the tree in O(1 +log(min{d,n-d} + 1)) time, where d is the number of items
between the two given items. The search proceeds up from the starting item following
parent pointers and level links until a subtree or two in which the desired item must
be located are found; then the search proceeds downward in the standard way. Simul-
taneously with the search from the given starting item, searches are performed start-
ing from the first and last items in the list; all three searches terminate when the
desired item is first located (or discovered not to be in the tree).
Homogeneous finger search trees support fast searches only with respect to the
total order on the items, not searches by position or searches based on secondary heap
order. On the other hand, the extra time needed to update level links is only O (1) per
local transformation (of the kinds in Figures 19 and 20), and thus the amortized time
bounds of insertion, deletion, concatenation, and splitting are the same in homogene-
ous trees as they are in heterogeneous trees. Furthermore, homogeneous trees support
a more drastic splitting operation, called three-way splitting: given two items x and y
in a tree T, remove from T the sublist of items from x to y (inclusive) to form two
trees, one representing the removed sublist and the other representing the remaining
items. The amortized time for a three-way splitting operation is

O(1 +log(min{d,n-d} + 1)), where d is the number of items in the removed sublist.
See [14] for details on how a three-way split can be performed within this time bound.
Acknowledgments. We thank Brenda Baker for her many helpful comments on

an earlier draft of this paper, and Bernard Chazelle for his thorough reading of this
version of the paper.
REFERENCES
[1] B. K. BHATTACHARYA AND G. T. TOUSSAINT, ,4 linear algorithm for determining the translation
separability of two simple polygons, Technical report SOCS 86 l, School of Computer Science, McGill
University, Montreal, Canada, 1986.
[2l M. R. BROWN AND R. E. TARJAN, Design and analysis of a data structure for representing sorted
lists, this Journal, 9 (1980), pp. 594-614.
[31 B. CHAZELLE, ,4 theorem on polygon cutting with applications, Proc. 23rd Annual Symp. on Found. of
Comput. Sci., 1982, pp. 339-349.
[4] Intersecting is easier than sorting, Proc. Sixteenth Annual ACM Symp. on Theory of Comput.,
1984, pp. 125-134.
[5] B. CHAZELLE AND J. INCERPl, Triangulation and shape complexity, ACM Trans. on Graphics, 3
(1984), pp. 135-152.
[6l W.-P. CHIN AND S. NTAFOS, Optimum watchman routes, Proc. Second Annual Symp. on Computa-
tional Geometry, 1986, pp. 24-33.
[7] D. P. DOBKIN, D. L. SOUVAINE AND C. J. VAN WYK, Decomposition and intersection of simple spline-
gons, Algorithmica, to appear.
[8] H. EDELSBRUNNER, L. J. GUIBAS AND J. STOLFI, Optimal point location in a monotone subdivision,
this Journal, 15 (1986), pp. 317-340.
[9] A. FOURNIER AND D. Y. MONTUNO, Triangulating simple polygons and equivalent problems, ACM
Trans. on Graphics, 3 (1984), pp. 153-174.
[10] M. R. GAREY, D. S. JOHNSON, F. P. PREPARATA AND R. E. TARJAN, Triangulating a simple polygon,
Inform. Process. Lett., 7 (1978), pp. 175-180.
[11] L. GUIBAS, J. HERSHBERGER, O. LEVEN, M. SHARIR AND R. E. TARJAN, Linear time algorithms for
visibility and shortest path problems inside triangulated simple polygons, Algorithmica, to appear.
[12] L. J. GUIBAS, E. M. MCCREIGHT, M. F. PLASS AND J. R. ROBERTS, ,4 new representation for linear
lists, Proc. Ninth Annual ACM Symp. on Theory of Comput., 1977, pp. 49-60.
13 S. HERTEL AND K. MEHLHORN, Fast triangulation of a simple polygon, Proc. Conf. Found. of Comput.
Theory, New York, Springer-Verlag, Berlin, 1983, pp. 207-218.
14] K. HOFFMAN, K. MEHLHORN, P. ROSENSTIEHL AND R. TARJAN, Sorting Jordan sequences in linear
time using level-linked search trees, Inform. and Control, 68 (1986), pp. 170-184.
[15]S. HUDDLESTON, An efficient scheme for fast local updates in linear lists, Dept. of Information and
Computer Science, University of California, Irvine, CA, 1981.
[16] S. HUDDLESTON AND K. MEHLHORN, A new data structure for representing sorted lists, Acta Inform.,
17 (1982), pp. 157-184.
[17] J. M. KEIL, Decomposing a polygon into simpler components, this Journal, 14 (1985), pp. 799-817.
[18]S. R. KOSARAJU, Localized search in sorted lists, Proc. Thirteenth Annual ACM Symp. on Theory of
Comput., 1981, pp. 62-69.
19] D. MAIER AND C. SALVETER, Hysterical B-trees, Inform. Process. Lett., 12 (1981), pp. 199-202.
[20]K. MEHLHORN, Data Structures and Efficient Algorithms, Volume 1: Sorting and Searching,
Springer-Verlag, Berlin, 1984.
[21] J. R. MUNKRES, Topology: A First Course, Prentice-Hall, Englewood Cliffs, NJ, 1975.
[22] A. A. SCHFFER AND C. J. VAN WYK, Convex hulls of piecewise smooth Jordan curves, J. Algorithms,
8 (1987), pp. 66-94.
[23] D. D. SLEATOR AND R. E. TARJAN, Self-adjusting binary search trees, J. Assoc. Comput. Mach., 32
(1985), pp. 652-686.
[24]D. L. SOUVAINE, Computational Geometry in a Curved World, Ph.D. dissertation, Department of
Computer Science, Princeton University, 1986.
[25]R. E. TARJAN, Data Structures and Network Algorithms, Society for Industrial and Applied
Mathematics, Philadelphia, PA, 1983.
[26] Amortized computational complexity, SIAM J. Algebraic and Discrete Methods, 6 (1985), pp.
306-318.
[27] R. E. TARJAN AND C. J. VAN WYK, A linear-time algorithm for triangulating simple polygons, Proc.
Eighteenth Annual ACM Symp. on Theory of Comput., 1986, pp. 380-388.
[28] A. K. TSAKALIDIS, AVL-trees for localized search, Automata, Languages, and Programming, lth Col-
loquium, J. Paredaens, ed., Lecture Notes in Computer Science 172, Springer-Verlag, Berlin, 1984, pp.
473-485.
[29] An optimal implementation for localized search, A84/06 Fachbereich Angewandte Mathema-
tik und Informatik, Universit/it des Saarlandes, Saarbriicken, West Germany, 1984.
[30] C. J. VAN WYK, Clipping to the boundary of a circular-arc polygon, Computer Vision, Graphics, and
Image Processing, 25 (1984), pp. 383-392.
[31] T. C. Woo AND S. Y. SHIN, A linear time algorithm for triangulating a point-visible polygon, ACM
Trans. on Graphics, 4 (1985), pp. 60-69.

1988 Tarjan Van Wyk

Uploaded by

Copyright:

Available Formats

1988 Tarjan Van Wyk

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

1988 Tarjan Van Wyk

Uploaded by

Copyright:

Available Formats

SIAM J. COMPUT.

(C) 1988 Society tbr Industrial and Applied Mathematics

AN O(n log log n)-TIME ALGORITHM FOR

1. Introduction. Let P be an n-vertex simple polygon, defined by a list

FIG. 3. Illustrating Steps and 4 of the visibility algorithm.

FIG. 6. The four cases for Jordan sorting.

FIG. 7. Modifications to make Jordan sorting error-correcting.

Y =Ymax TOP TOP TOP

Let us examine the manipulations of the boundary data structures required to

inside a simple polygon. By the linear-time reduction of triangulation to the visibility

(iii) a subregion is constructed in Step 4 whose side boundary segments, say S

FIG. 23. The pointers in a homogeneous red-black finger search tree.

items. The amortized time for a three-way splitting operation is

Acknowledgments. We thank Brenda Baker for her many helpful comments on

You might also like