An efficient algorithm for finding the CSG representation of a simple polygon.
We consider the problem of converting boundary representations of polyhedral objects into constructive-solid-geometry (CSG) representations. The CSG representations for a polyhedron P are based on the half-spaces supporting the faces of P. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practical O(n log n) algorithm for doing this boundary-to-CSG conversion for a simple polygon of n sides. We also prove that such nice formul&aelig; do not always exist for general polyhedra in three dimensions.
desirable that such representations be compact and support efficient simulation of real-world
operations on the objects. Over the years two different styles of representation have
emerged; these are used by nearly all geometric modeling systems currently in existence.
The first style of representation describes an object by the collection of surface elements
forming its boundary: this is a boundary representation. In effect, boundary representations
reduce the problem of representing a solid object to one of representing surface elements.
This is a somewhat simpler problem, since it is set in one dimension less. The second
style of representation describes a solid object as being constructed by regularized boolean
operations on some simple primitive solids, such as boxes, spheres, cylinders, etc. Such
a description is referred to as a constructive solid geometry representation, or CSG rep-
resentation, for short. Each style of representation has its advantages and disadvantages,
depending on the operations we wish to perform on the objects. The reader is referred to
one of the standard texts in solid modeling [13, 16], or the review article [23] for further
details on these representations and their relative merits.
If one looks at modelers in either camp, for example the romulus [16], geomod [25],
and medusa [17] modelers of the boundary persuasion, or the padl-1 [27], padl-2 [2],
and gmsolid [1] modelers of the CSG persuasion, one nearly always finds provisions for
converting to the other representation. This is an important and indispensable step that
poses some challenging computational problems 1 . In this paper we will deal with certain
cases of the boundary-to-CSG conversion problem and present some efficient computational
techniques for doing the conversion. Our approach is based on that of Peterson [21].
Peterson considered the problem of obtaining a CSG representation for simple polyhedral
solids, such as prisms or pyramids (not necessarily convex), based on the half-spaces
supporting the faces of the solid. Such solids are, in effect, two-dimensional objects (think
of the base of the prism or pyramid) in which the third dimension has been added in a very
simple manner. Thus Peterson considered the problem of finding CSG representations for
simple polygons in the plane. related problem is that of finding convex decompositions
of simple polygons [4, 18, 20, 26, 28].) By a complicated argument, Peterson proved that
every simple polygon in the plane admits of a representation by a boolean formula based on
the half-planes supporting its sides. This formula is especially nice in that each of the supporting
half-planes appears in the formula exactly once, and hence the formula is monotone
(no complementation is needed). For this reason we focus our attention on such formulae,
which we call Peterson-style formulae.
A monotone formula for a polygon or polyhedron is desirable because it makes it possible
to predict how small perturbations of the defining half-spaces affect the overall volume. This
is an important property in various applications of solid modeling, such as machine tooling.
When machining a peg that has to fit in a hole, for example, it is important to know that
any errors in the position of the defining half-spaces will result in making the peg only
smaller. If a half-space and its negation both enter a formula, then a perturbation of the
defining plane can make the volume smaller in one part of the object and simultaneously
To quote from Requicha [23]: ".the relative paucity of known conversion algorithms poses significant
constraints on the geometric modeling systems that we can build today."
larger in another part.
In this paper we first give a short new proof that every polygon has a Peterson-style
formula (Section 3). Peterson did not explicitly consider algorithms for deriving this CSG
representation from the polygon. A naive implementation based on his proof would require
for the conversion, where n is the size (number of sides or vertices) of the polygon.
We provide in this paper an efficient \Theta(n log n) algorithm for doing this boundary-to-CSG
conversion (Section 4). We regard this algorithm as the major contribution of our paper;
the algorithm uses many interesting techniques from the growing field of computational
geometry [5, 22]. Nevertheless, it is very simple to code-its subtlety lies in the analysis of
the performance and not in the implementation. Finally (Section 5), we show that Peterson-
style formulae are not always possible for general polyhedra in three dimensions and discuss
a number of related issues.
We believe that the work presented in this paper illustrates how several of the concepts
and techniques of computational geometry can be used to solve problems that are of clear
importance in solid modeling and computer graphics. The solution that we obtain is both
mathematically interesting and practical to implement. We expect to see more such applications
of computational geometry to other areas in the future and hope that this paper will
motivate some researchers in the graphics area to study computational geometry techniques
more closely.
Formulation and history of the problem
Let P be a simple polygon in the plane; in this context, simple means non-self-intersecting.
By the Jordan curve theorem, such a polygon subdivides the plane into two regions, its
interior and its exterior. In general, we identify the polygon with its interior. Let us orient
all the edges of P so that the interior of P lies locally to the right of each edge, and give
each such oriented edge a name. We will call these names literals. To each literal we also
give a second meaning. A literal m also represents the half-plane bounded by the infinite
line supporting the edge m and extending to the right of that line. We will speak of such a

Figure

1: A simple polygon
P and the half-plane supporting
side m
half-plane as supporting the polygon (even though P might
not all lie in the half-plane). See Figure 1 for an illustration
of these concepts.
Notice that, for each point x of the plane, if we know
whether x lies inside or outside each of the half-planes supporting
, then we know in fact if x is inside P . This fol-
lows, because each of the regions into which the plane is
subdivided by the infinite extensions of the sides of P lies
either wholly inside P , or wholly outside it. As a result,
there must exist a boolean formula whose atoms are the
literals of P and which expresses the interior of P . For
example, if P is convex, then this formula is simply the
"and" of all the literals.
Since "and"s and "or"s are somewhat cumbersome to write, we will switch at this point
to algebraic notation and use multiplication conventions for "and" and addition conventions
for "or". Consider the two simple polygons shown in Figure 2. Formulae for the two polygons
are uv(w(x polygon (a) and uvw(x (b). The associated
boolean expression trees are also shown in Figure 2. Notice that these are Peterson-style
formulae: they are monotone and use each literal exactly once. The reader is invited at this
point to make sure that these formulae are indeed correct.
(a)
(b)
x
y
z
x
z
y
y
x z
z
y
x

Figure

2: Formulae for two polygons
A more complex formula for a simple polygon was given by Guibas, Ramshaw, and
Stolfi [9] in their kinetic-framework paper. That style of formula for the two polygons of

Figure

2 is uv \Phi vw \Phi wx \Phi xy \Phi yz \Phi zu. Here \Phi denotes logical "xor" and the overbar
denotes complementation. As explained in [9], that type of formula is purely local, in that it
depends only on the convex/concave property of successive angles of the polygon. The rule
should be obvious from the example: as we go around, we complement the second literal
corresponding to a vertex if we are at a convex angle, and the first literal if we are at a
concave angle. Thus the formula is the same for both of the example polygons.
Although a formula of this style is trivial to write down, it is not as desirable in solid
modeling as a Peterson-style formula, because of the use of complementation and the "xor"
operator. The Peterson formula is more difficult to derive, because it captures in a sense how
the polygon nests within itself and thus is more global in character. It can be viewed naively
as an inclusion-exclusion style formula that reflects this global structure of the polygon. We
caution the reader, however, that this view of the Peterson formula is too naive and led us
to a couple of flawed approaches to this problem.
In general there are many boolean formulae that express a simple polygon in terms of
its literals. Proving the equivalence of two boolean formulae for the same polygon is a
non-trivial exercise. The reason is that of the 2 n primitive "and" terms one can form on
literals (with complementation allowed), only \Theta(n 2 ) are non-zero, in the sense that they
denote non-empty regions of the plane. Thus numerous identities hold and must be used
in proving formula equivalence.
The decomposition of a simple polygon into convex pieces [4, 18, 20, 26, 28] gives another
kind of boolean formula for the polygon, one in which the literals are not half-planes, but
convex polygons. Depending on the type of decomposition desired, the convex polygons
may or may not overlap; in the overlapping case, the formula may or may not contain
negations. If we expand the literals in a convex decomposition into "and"s of half-planes,
the result need not be a Peterson-style formula: negations, repeated literals, and half-planes
that do not support the polygon are all possible.
If we leave the boolean domain and allow algebraic formulae for describing the characteristic
function of a simple polygon, then such formulae that are purely local (in the same
sense as the "xor" formula above) are given in a paper of Franklin [6]. Franklin describes
algebraic local formulae for polyhedra as well. We do not discuss this further here as it goes
beyond the CSG representations we are concerned with.
3 The existence of monotone formulae
In this section we will prove that the interior of every simple polygon P in the plane can be
expressed by a Peterson-style formula, that is, a monotone boolean formula in which each
literal corresponding to a side of P appears exactly once.
As it turns out, it is more natural to work with simple bi-infinite polygonal chains (or
chains, for short) than with simple polygons. An example of a simple bi-infinite chain c is
shown in Figure 3. Such a chain c is terminated by two semi-infinite rays and in between
contains an arbitrary number of finite sides. Because it is simple and bi-infinite, it subdivides
the plane into two regions. We will in general orient c in a consistent manner, so we can
speak of the region of the plane lying to the left of c, or to the right of c, respectively. By
abuse of language, we will refer to these regions as half-spaces.
left half-space
the semi-infinite rays
right half-space
a
c
d
e
f
l

Figure

3: A simple bi-infinite chain
The interior of a simple polygon P can always be viewed as the intersection of two such
chain half-spaces. Let ' and r denote respectively the leftmost and rightmost vertex of P .
As in

Figure

4, extend the sides of P incident to ' infinitely far to the left, and the sides
incident to r infinitely far to the right. It is clear that we thus obtain two simple bi-infinite
chains and that the interior of P is the intersection of the half-space below the upper chain
with the half-space above the lower chain. Notice also that the literals used by the upper
and lower chains for these two half-spaces form a partition of the literals of P . Thus it
suffices to prove that a chain half-space admits of a monotone formula using each of its
literals exactly once.
l
r
upper chain
lower chain

Figure

4: The interior of a simple polygon P
If a chain consists of a single line, then the claim is trivial: the formula is the single
literal that defines the line.
If a chain c has more than one edge, we prove the claim by showing that there always
exists a vertex v of c such that if we extend the edges incident to v infinitely far to the other
side of v, these extensions do not cross c anywhere. In particular, the extensions create two
new simple bi-infinite chains c 1 and c 2 that, as before, partition the literals used by c. See

Figure

5 for an example. It is easy to see that the half-space to the right (say) of c is then
either the intersection or the union of the half-spaces to the right of c 1 and c 2 . It will be
the intersection if the angle of c at v in the selected half-space is convex (as is the situation
in

Figure

5), and the union if this angle is concave.
The existence of the desired vertex v is relatively easy to establish. Of the two half-spaces
defined by c there is one that is bounded by the two semi-infinite rays in a "convex"
fashion. What we mean by this is that when we look at this half-space from a great distance
above the xy-plane (so we can discern only the semi-infinite rays bounding it) it appears as
a convex angle ( ). For example, in Figure 5, the right half-space R of c is the convex
one. Now consider the convex hull h(R), the intersection of all half-planes containing R.
This hull is an unbounded polygonal region whose vertices are vertices of c. Clearly at least
one vertex of c lies on h(R), and any such vertex is a good vertex at which to break c; that
is, it can serve as the vertex v of the previous argument. The reason is clear from Figure 6:
at any such vertex the extensions of the sides incident upon it cannot cross c again.
It is worth remarking here that the determination of the splitting vertex v in the manner
above is not at all influenced by whether we are trying to obtain a boolean formula for the
right half-space of c or the left half-space of c. The choice of which half-space to take the
convex hull of is determined solely by the behavior of the semi-infinite rays of c. Indeed, if we
were to choose the wrong ("concave") half-space, its convex hull would be the whole plane
and would contain no vertices. We can summarize the situation by saying that we always
R
c
chainc
chain
Figure

5: The splitting vertex v for a chain c
R
c

Figure

The convex hull h(R)
split at a vertex of the convex hull of the polygonal chain c; this definition automatically
selects the correct half-space.
By recursively applying this decomposition procedure until each subchain becomes a
single bi-infinite straight line we can derive the following theorem.
Theorem 3.1 Every half-space bounded by a simple bi-infinite polygonal chain has a monotone
boolean formula using each of the literals of the chain exactly once. The same holds
for the interior of any finite simple polygon.
If we are given a polygonal chain c, such as the one in Figure 3, then certain aspects
of the boolean formula of (say) the right half-space R of c can be immediately deduced by
inspection. For example, it follows from the arguments above that there exists a boolean
formula for R that not only uses each literal exactly once, but in fact contains these literals
in the order in which they appear along c; if we were to omit the boolean operators and
parentheses in the formula, we would just get a string of all the literals in c in order.
Furthermore, the boolean operators between these literals are easy to deduce. As the
previous discussion makes clear, between two literals that define a convex angle in R the
corresponding operator has to be an "and", and between two literals that define a concave
angle the corresponding operator has to be an "or". Thus, with parentheses omitted, the
boolean formula for the chain c in Figure 3 has to look like a
a
c
e
f d

Figure

7: Our methods cannot
obtain all valid formulae
for this polygon
The preceding paragraph shows that the crux of the
difficulty in computing a boolean formula is to obtain the
parenthesization, or equivalently, the sequence of the appropriate
splitting vertices. We call this the recursive chain-
splitting problem for a simple bi-infinite chain. The solution
of this problem is the topic of the next section. For
the chain of Figure 3 a valid solution is
We conclude by noticing that a procedure for solving
this problem may be non-deterministic, since in general we
will have a choice of several splitting vertices. We can in
fact simultaneously split at any subset of them. Still, not
all valid Peterson-style formulae for a simple polygon are
obtained in this fashion. Our formulae all have the property
that the literals appear in the formula in the same
order as in the polygon. Figure 7 shows an example of a
Peterson-style formula where that is not true: a valid formula for the polygon shown is
4 The conversion algorithm
We have seen in Section 3 that we can find a monotone boolean formula for a simple polygon
if we can solve the following recursive chain-splitting problem:
Given a simple bi-infinite polygonal chain with at least two edges, find a vertex
z of its convex hull. Split the chain in two at z and extend to infinity the two
edges incident to z, forming two new chains. Because z is on the convex hull,
both chains are simple. Recursively solve the same problem for each chain that
has at least two edges.
We present an O(n log n) algorithm to solve this chain-splitting problem, where n is the
number of vertices of the polygon P . The algorithm uses only simple data structures and
is straightforward to implement.
Before we describe our algorithm, let us consider a naive alternative to it. Many algorithms
have been published that find the convex hull of a simple polygon in linear
time [7, 15, 11, 14, 24]. With slight modifications, any of these algorithms can be used
to find a vertex on the hull of a simple bi-infinite polygonal chain. If we use such an algorithm
to solve the chain-splitting problem, the running time is O(n) plus the time needed
to solve the two subproblems recursively. The worst-case running time t(n) is given by the
recurrence
0!k!n
which has solution
(a)
(b)

Figure

8: Two
paths with worst-case
and best-case
splitting behavior
This quadratic behavior occurs in the worst case, shown in Figure
8a, because each recursive step spends linear time splitting a
single edge off the end of the path. In the best case, on the other
hand, each split divides the current path roughly in half, and the
algorithm runs in O(n log n) time. This asymptotic behavior can be
obtained for the path shown in Figure 8b, if the splitting vertices are
chosen wisely.
The best case of this naive algorithm is like a standard divide-and-
conquer approach: at each step the algorithm splits the current path
roughly in half. In general, however, it is difficult to guarantee an
even division, since all vertices on the convex hull might be extremely
close to the two ends of the path. Thus, to avoid quadratic behavior,
we must instead split each path using less than linear time. Other
researchers have solved similar problems by making the splitting cost
depend only on the size of the smaller fragment [8, 10]. If the running
time t(n) obeys the recurrence
0!k!n
then log n). Our method uses a similar idea: the splitting cost is O(log n) plus
a term that is linear in the size of one of the two fragments. The fragment is not necessarily
the smaller of the two, but we can bound its size to ensure an O(n log n) running time
overall. The details of this argument appear in Section 4.5.
We present our algorithm in several steps. We first give a few definitions, then give an
overview of our approach. We follow the informal overview with a pseudo-code description
of the algorithm. Section 4.3 gives more detail about one of the pseudo-code operations,
and Section 4.4 describes the data structure used by the algorithm. Section 4.5 concludes
the presentation of the algorithm by analyzing its running time.
4.1 Definitions
As shown in Section 3, we can find a boolean formula for P by splitting the polygon at its
leftmost and rightmost vertices to get two paths, then working on the two paths separately.
We denote by  the current path, either upper or lower. If u and v are vertices of , we use
the notation (u; v) to refer to the subpath of  between u and v, inclusive. The convex
hull of a set of points A is denoted by h(A); we use h(u; v) as shorthand for h((u; v)). A
path (u; v) has j(u; v)j edges; similarly, jh(u; v)j is the number of edges on h(u; v).
We can use the path (u; v) to specify a bi-infinite chain by extending its first and
last edges. Let e u be the edge of (u; v) incident to u, and let * e u be the ray obtained
by extending e u beyond u. Let e v and * e v be defined similarly. Then (u; v) specifies the
bi-infinite polygonal chain obtained by replacing e u by * e u and e v by * e v . In general, for
arbitrary u and v, this bi-infinite chain need not be simple. Our algorithm, however, will
guarantee the simplicity of each bi-infinite chain it considers. We assume in what follows
that * e u and * e v are not parallel, which guarantees that the convex hull of the bi-infinite
chain has at least one vertex. A slight modification to the algorithm is needed if the rays
are parallel.
4.2 The algorithm
This section presents the algorithm that recursively splits a polygonal chain. We first outline
the algorithm and then present it in a pseudo-code format. Subsequent sections give the
details of the operations sketched in this section.
We now outline the algorithm. Given a polygonal path (u; v) with at least two edges,
we partition it at a vertex x to get two pieces (u; x) and (x; v) with roughly the same
number of edges. The vertex x is not necessarily a vertex of h(u; v); this partitioning is
merely preparatory to splitting (u; v) at a hull vertex. In O(j(u; v)j) time we compute
the convex hulls of (u; x) and (x; v) in such a way that for any vertex z of (u; v), we
can easily find h(x; z). Our data structure lets us account for the cost of finding h(x; z) as
part of the cost of building h(u; x) and h(x; v). The details of this accounting appear in
Section 4.5.
The next step of the algorithm locates a vertex z of the convex hull of the bi-infinite
chain (u; v)[ * e u [ * e v . We will split (u; v) at z. The vertex z can be on the path (u; x) or
on the path (x; v). Without loss of generality let us assume that z is a vertex of (u; x);
because u is not a vertex of the convex hull, z 6= u. We recursively split (u; z), partitioning
it at its midpoint, building convex hulls, and so on. However, and this is the key observation,
we do not have to do as much work for (z; v) if z 6= x. We already have the hull h(x; v),
and we can easily find h(z; x) from our data structure for h(u; x). Thus we can recursively
split (z; v) without recomputing convex hulls. Intuitively speaking, we do a full recursion
(including convex hull computation) only on pieces whose length is less than half the length
of the piece for which we last computed convex hulls.
The key to our algorithm's efficiency is avoiding the recomputation of convex hulls. The
naive algorithm builds O(n) hulls whose average size can be as much as n=2; our algorithm
also builds O(n) hulls, but their average size is only O(log n). Our algorithm locates n
splitting vertices in O(log n) time apiece, which contributes another O(n log n) term to the
running time. These two terms dominate the time cost of the algorithm, as Section 4.5
shows.
We present the algorithm more formally in the pseudo-code below. The pseudo-code represents
a convex hull h(x; v) using a data structure called a path hull, denoted by PH (x; v);
the path hull stores the vertices of h(x; v) in a linear array. The algorithm uses the path hull
PH (x; v) to produce PH (x; z) efficiently, for any splitting vertex z in (x; v). The algorithm
consists of two mutually recursive subroutines, f() and p(), whose names stand for full and
partial. The routine f(u; v) partitions (u; v) at x to get two equal parts, builds a path
hull structure for each, and calls p(u; x; v). The subroutine p(u; x; v) uses PH (x; u) and
PH (x; v) to find the splitting vertex z; Section 4.3 gives the details of this operation. The
routine then splits (u; v) at z and recurses on each fragment; it ensures that the required
path hulls have been built whenever p() is called. We start the algorithm by invoking f()
on the entire path .
begin
1. if (u; v) is a single edge then return;
else
begin
2. Let x be the middle vertex of (u; v);
3. Build PH (x; u) and PH (x; v);
4. p(u; x; v);
p(u; x; v) /* x is a vertex of (u; v), not equal to u
or v. Path hulls PH (x; v) and PH (x; u)
have been computed. */
begin
5. Find a vertex z of h((u; v)[ * e u [ * e v ). Output z as part of the sequence of
splitting vertices.
else
begin
7. if z 2 (u; x) then build PH (x; z) from PH (x; u);
else build PH (x; z) from PH (x; v);
if z is a vertex of (u; x) then
8. begin f(u; z); p(z; x; v); end
else
9. begin p(u; x; z); f(z; v); end
The chain-splitting algorithm
4.3 Finding a splitting vertex
This section shows how to use the path hull data structure to find the splitting vertex z.
Our method exploits the fact that PH (x; v) represents h(x; v) as a linear array of convex
hull vertices: we perform binary search on the array to find the splitting vertex.
Given a path (u; v), we want to find a vertex of the convex hull of the bi-infinite chain
that (u; v) specifies. Each such vertex belongs to the finite convex hull h(u; v); we solve
our problem by finding a vertex of h(u; v) that is guaranteed to belong to the infinite hull.
The edges of the infinite hull h((u; v) [ * e u [ * e v ) have slopes in a range bounded by the
slopes of * e u and * e v . Vertices of the hull have tangent slopes in the same range. We simply
find a vertex of h(u; v) with a tangent slope in the range. Let d u and d v be the direction
vectors of the rays * e u and * e v . Because * e u and * e v are not parallel, d u and d v define an
angular range of less than 180 degrees; define d to be the negative of the bisector of this
angular range. An extreme vertex of h(u; v) in direction d is guaranteed to be a vertex of
the infinite hull. 2 See Figure 9 for an example.
d d
d

Figure

9: We find an extremal vertex in the direction d
We use binary search on each of the two path hulls PH (u; x) and PH (x; v) to find an
extreme vertex in direction d. We compare the two vertices and pick the more extreme of
the two. If we break ties consistently in the binary searches and in the comparison of the
two extreme vertices (say, by preferring the left vertex of tied pairs), the vertex we find is
guaranteed to be a vertex of the infinite hull.
4.4 Implementing path hulls
In this section we describe the path hull data structure used in the previous two sections.
The path hull PH (x; v) represents the convex hull of (x; v). It is not symmetric in its ar-
guments: it implicitly represents h(x; v 0 ) for all vertices v 0 in (x; v), but does not represent
not equal to x. The structure PH (x; v) has three essential properties:
1. PH (x; v) represents h(x; v) by a linear array of vertices. Let " v be the vertex of h(x; v)
closest to v on (x; v). Then the array lists the vertices of h(x; v) in clockwise order,
starting and ending with " v.
2. Given PH (x; v), we can transform it into PH (x; v 0 ) for any vertex v 0 in (x; v),
destroying PH (x; v) in the process. Let the vertices of (v; x) be numbered
successively transform PH (x; v) into PH (x; v i ) for each v i
in sequence from v time proportional to j(x; v)j.
3. PH (x; v) can be built from (x; v) in O(j(x; v)j) time.
We get these properties by adapting Melkman's algorithm for finding the convex hull of
a polygonal path [15]. We satisfy requirement 2 by "recording" the actions of Melkman's
algorithm as it constructs h(x; v), then "playing the tape backwards."
To avoid computing square roots, in practice we do not compute the bisector of the angle defined by du
and dv . Instead, we find the normals to du and dv that point away from the infinite hull, then add the two
to get a direction d strictly between these normals.
Many linear-time algorithms have been proposed to find the convex hull of a simple
polygon [7, 15, 11, 14, 24]. Some of these algorithms need to find a vertex on the hull
to get started; we use Melkman's algorithm because it does not have this requirement. It
constructs the hull of a polygonal path incrementally: it processes path vertices in order,
and at each step it builds the hull of the vertices seen so far.
The algorithm keeps the vertices of the current convex hull in a double-ended queue, or
deque. The deque lists the hull vertices in clockwise order, with the most recently added
hull vertex at both ends of the deque. Let the vertices in the deque be
. The algorithm operates on the deque with push and pop operations that
specify the end of the queue, bottom or top, on which they operate. The algorithm appears
below; it assumes that no three of the points it tests are collinear, though this restriction
is easy to lift.
Get the first three vertices of the path with the function NextVertex() and put
them into the deque in the correct order.
while v / NextVertex() returns a new vertex do
if v is outside the angle
begin
while v is left of \Gamma\Gamma\Gamma* v b v b+1 do pop(v b ; bottom);
while v is left of \Gamma\Gamma\Gamma* v
Melkman's convex hull algorithm

Figure

if it lies in the shaded
sector
We now sketch a proof of correctness; Melkman gives a full
proof [15]. We first consider the case in which the vertex v is
discarded. This happens when v is inside the angle
(See

Figure

10.) We know that v b+1 is connected to v t\Gamma1 by a
polygonal path, and that v is connected to v b by a polygonal path.
The two paths do not intersect, so v must lie inside the current
hull. When v is not discarded, it lies outside the current hull, and
the algorithm pops hull vertices until it gets to the endpoints of
the tangents from v to the current hull. The algorithm is linear:
if it operates on a path with n vertices, it does at most 2n pushes
and pops.
We can use the algorithm to build an array representation of
the hull. The algorithm does at most n pushes at either end of the
deque, so we can implement the deque as the middle part of an
array of size 2n. Pushes and pops increment and decrement the array indices of the ends of
the queue; pushes write in a new element, pops read one out. The resulting deque contains
the vertices of the convex hull in a contiguous chunk of an array.
As we have described it so far, the array data structure has path hull properties 1 and 3;
how can we obtain property 2? When the algorithm builds h(x; v) starting from x and
working toward v, at intermediate steps it produces h(x; v 0 ) for every vertex v 0 in (x; v).
We need to be able to reconstruct these intermediate results. To do this, we add code to
the algorithm to create a transcript of all the operations performed, recording what vertices
are pushed and popped at each step. The structure PH (x; v) stores not only the deque
that represents h(x; v), but also the transcript of the operations needed to create the deque
from scratch. To reconstruct PH (x; v 0 ) from PH (x; v), we read the transcript in reverse
order, performing the inverse of each recorded operation (pushing what was popped, and
vice versa), until the deque represents h(x; v 0 ). We throw away the part of the transcript
we have just read, so that PH (x; v 0 ) stores only the transcript of the operations needed to
create Because we discard every step we have read over, we look at each step of the
transcript at most once during the playback. Therefore, reconstructing the intermediate
results takes time proportional to the original cost of finding PH (x; v). This completes the
proof that the path hull data structure has all three of its required properties.
4.5 Analyzing the running time
In this section we analyze the running time of the chain-splitting algorithm given on page 10.
The analysis uses a "credit" scheme, in which each call to f() or p() is given some number
of credits to pay for the time used in its body and its recursive calls. We give O(n log n)
credits to the first call to f (), then show that all calls have enough credits to pay for their
own work and that of their recursive calls.
We begin the analysis by proving that f() and p() are called O(n) times: Every call
to p(u; x; v) splits (u; v) into two non-trivial subpaths, and every call to f(u; v) for which
(u; v) has more than one edge passes (u; v) on to p(). The initial path  can be split only
O(n) times, so the recursion must have O(n) calls altogether.
How much work is done by a call to f(u; v), exclusive of recursive calls? We assume
that the vertices of  are stored in an array. Therefore line 2 of f() takes only constant
time. Line 3 is the only step of f() that takes non-constant time; as shown in Section 4.4,
line 3 takes O(j(u; v)j) time. We define the value of a credit by saying that a call f(u; v)
needs j(u; v)j credits-one credit per edge of (u; v)-to pay for the work it does, exclusive
of its call to p(). The constant-time steps in f() take O(n) time altogether and hence are
dominated by the rest of the running time.
A call to p(u; x; v) does accountable work in lines 5 and 7. The cost of line 5 is dominated
by two binary searches, which take O(log n) time. Line 5 therefore takes O(n log n) time over
the whole course of the algorithm. Section 4.4 shows that the cost of building PH (x; z) at
line 7 can be accounted as part of the construction cost of the path hull from which PH (x; z)
is derived. Thus we can ignore the work done at line 7 of p(); its cost is dominated by that
of line 3 of f ().
To complete our analysis of the running time, we must bound the cost of all executions
of line 3 of f (). In a single call to f(u; v), line 3 uses j(u; v)j credits. The sum of all credits
used by line 3 is proportional to the time spent executing that line. We give ndlog 2 ne
credits to the first call to f (), then show that this is enough to pay for all executions of
line 3. We use the following two invariants in the proof:
1. A call to f(u; v) is given at least mdlog 2 me credits, where to pay for
itself and its recursive calls.
2. A call to p(u; x; v) is given at least (l
and to pay for its recursive calls.
Lemma 4.1 If a call to f() or p() is given credits in accordance with invariants 1 and 2,
it can pay for all executions of line 3 it does explicitly or in its recursive calls.
Proof: Let m, l, and r be as defined above. The proof is by induction on m.
A call to f(u; v) with no credits and needs none, since it does not
reach line 3. There are no calls to p() with
A call to f(u; v) with m ? 1 gets at least mdlog 2 me credits and spends m
of them executing line 3. It has mdlog 2 (m=2)e to pass on to its call to p(u; x; v).
The larger of l and r is dm=2e, and dlog 2 dm=2ee, so the call to
gets at least mdlog 2 credits, as required
by invariant 2.
A call to p(u; x; v) splits (u; v) into two paths (u; z) and (z; v) with a
and b edges, respectively. The call to p(u; x; v) divides its credits between its
recursive calls evenly according to subpath size. If z = x, then the two calls
to f() get at least ldlog 2 max(l; r)e  ldlog 2 le and rdlog 2 max(l; r)e  rdlog 2 re
credits, satisfying invariant 1. If z 6= x, then without loss of generality assume
that z belongs to (u; x) and line 8 is executed; the other case is symmetric. The
call to f(u; z) gets at least adlog 2 max(l; r)e  adlog 2 ae, as required. The call
to p(z; x; v) gets at least bdlog 2 max(l; r)e  bdlog 2 max(b \Gamma r)e, as required by
invariant 2. This completes the proof.
Altogether the calls to f() and p() take O(n log n) time, plus the time spent building
path hulls at line 3. The preceding lemma shows that all the executions of line 3 take only
O(n log n) time, and hence the entire algorithm runs in O(n log n) time.
4.6 Implementation
The algorithm described in this section has been implemented. The implementation is
more general than the algorithm we have so far described: it correctly handles the cases of
collinear vertices on convex hulls and parallel rays on bi-infinite chains. These improvements
are not difficult. Handling collinear vertices requires two changes: the program detects and
merges consecutive collinear polygon edges, reporting them to the user, and the while loop
tests in Melkman's algorithm are changed from ``v is left of '' to "v is on or to the left
of the line supporting." When a chain has parallel infinite rays, its convex hull may be
bounded by two infinite lines. Even though the hull has no vertices, the chain nevertheless
has valid splitting vertices on the hull. The program finds a splitting vertex by searching
for an extreme vertex in a direction perpendicular to the infinite rays, using a special case
to avoid selecting u or v.
As input the program takes a list of polygon vertices in order (either clockwise or
counterclockwise), specified as x-y coordinate pairs. As output the program produces a
Figure

displayed as a polygon
list of the splitting vertices in the order they are computed; it also produces a correctly
parenthesized boolean formula for the input polygon. When the program is applied to the
polygon shown in Figure 11, it produces the following (slightly abbreviated) output:
main: Calling f() on 8.17
p: splitting at vertex 16, 15, 9, 10, 13, 11,
main: Calling f() on 17.25, 0.8
p: splitting at vertex 18, 19, 20, 0, 25, 24,
Boolean formula is:
In this formula, the number i refers to the edge joining vertex i to vertex (i
here n is 26.
The program produces graphical as well as textual output. Marc H. Brown created
the graphical displays using an algorithm animation system he is developing at the DEC
Systems Research Center. (Brown's thesis [3] provides more information on algorithm
animation.) The animation shows multiple color views of the state of the computation,
which are updated as the program runs. One view shows the input polygon and highlights
chains, convex hulls, and splitting vertices as the algorithm operates on them. Another view
pictorially displays the formula for each subchain as a boolean combination of half-planes.
Other views show the incremental construction of the boolean formula and its parse tree.
Each view emphasizes a different aspect of the algorithm; together they illuminate many of
its important features.
The title page of this report shows a black-and-white snapshot of the animated algorithm
running on a small example. The snapshot features three views of the algorithm.
The "Geometry" view shows the polygon; in the snapshot, this view highlights the initial
splitting vertices. The "Formula" view shows the development of the boolean formula over
time. The "CSG Parse Tree" view shows the parse tree corresponding to the formula; each
node of the tree displays the region that corresponds to the subtree rooted at the node.
5 Formulae for polyhedra
We have shown that the interior of a simple polygon can be represented by a Peterson-style
formula: a monotone boolean formula that uses each literal once. We would like to find
such a formula for a polyhedron P in 3-space. Here, the literals are half-spaces bounded by
the planes supporting the faces.
In this section we prove that not all polyhedra have a Peterson-style formula. Figure 12
illustrates a simplicial polyhedron (each face is a triangle) with eight vertices and twelve
faces. Six of the faces are labeled; the six unlabeled faces lie on the convex hull of P .
The edge between C and C 0 is a convex angle. The half-spaces defined by faces A and B
intersect the faces A 0 and B 0 . Similarly, the half-spaces defined by A 0 and B 0 intersect faces
A and B. After we establish a couple of lemmas, we will prove that P has no Peterson-style
formula by assuming that it has one and deriving a contradiction.
We begin by observing that any collection of planes divides space into several convex
regions. (In the mathematical literature, this division is usually called an arrangement [5].)
If a polyhedron P has a CSG representation in terms of half-spaces, then we can specify a
subset of the planes bounding these half-spaces and derive a representation for the portion
of P inside any convex region determined by the subset.
More precisely, let f be a boolean formula whose literals are the half-spaces of P ; we
can think of f as an expression tree. If the tree for f has nodes a and b, then we denote the
lowest common ancestor of a and b in f by lca f (a; b). Let H Hm be a subset of the
half-spaces defined by faces of P . Each point in space can be assigned a string ff 2 f0; 1g m
such that the i-th character of ff is 1 if and only if the point is in half-space H i . All the
points assigned the string ff are said to be in the region R ff . We use f j ff to denote the
formula obtained by setting each H and simplifying the result by using algebraic
rules: a. The expression
tree for f j ff inherits several important properties from the expression tree for f :
Lemma 5.1 Let f be a formula that uses the half-spaces H
others) and let ff be a string in f0; 1g m . Then the derived formula f j ff has the following
three properties:
1. If f is monotone, then so is f j ff . Similarly, if f is Peterson-style, so is f j ff .
2. If the expression tree for f j ff has nodes a, b, and c, with
(a; b), then
in the tree for f .
A
C'
A'
A'

Figure

12: Two views of a simplicial polyhedron with no Peterson-style formula
3. If the expression tree for f j ff contains a node c at depth k, then the tree for f contains
the node c at depth  k.
Proof: All three properties are maintained by the rules that form the expression
tree for f j ff by simplifying the expression tree for f .
The next lemma shows the interaction between the region R ff and boolean formulae f j ff .
Lemma 5.2 If a polyhedron P has a formula f that uses half-spaces H
others) then, for any string ff 2 f0; 1g m , the portion of P inside the region R ff is described
by the formula f j ff .
Proof: The statement above simply says that formulae f and f j ff agree inside
the region R ff . This follows from the definition of f j ff and the fact that the
simplification rules do not change the value of the formula.
Two corollaries of Lemma 5.2 give us constraints on the formula of a polyhedron based
on its edges and faces. In these corollaries and the discussion that follows, we will add an
argument to a formula f j ff to emphasize which half-spaces are not fixed by the string ff.
Corollary 5.3 Let P be a polyhedron with Peterson-style formula f . If faces A and B of P
meet at an edge of P , the operator in f that is the lowest common ancestor of A and B,
lca f (A; B), is an "and" if and only if A and B meet in a convex angle.
Hm be the half-spaces of P except for the two defined
by A and B. Choose an interior point of the edge formed by faces A and B,
and let ff be its string. The two-variable formula f j ff (AB) must describe the
polyhedron in the vicinity of the edge, so by Lemma 5.1(2), lca f (A; B) is an
"and" if and only if A and B meet in a convex angle.
Corollary 5.4 Let P be a polyhedron with a Peterson-style formula f using half-spaces
and A and B. If the half-space defined by face B intersects face A at some
point with string ff then f j ff A.
Proof: The two-variable formula f j ff (AB) must describe the face A both inside
and outside the half-space of B, so B cannot appear in the formula.
Now we are ready to look at the polyhedron P in Figure 12. Suppose P has a Peterson-
style formula f . Then it has a formula f j 111111 (ABCA describes the region inside
the unlabeled faces. We look at the constraints on this formula and derive a contradiction.
Consider the three faces A, B, and C. By Corollary 5.3 we know that lca f (B;
and lca f 5.4 applied to faces A and C implies that the formula
describing these three faces is
where the string ff 1 appropriately fixes all the half-spaces except A, B, and C. Similarly,
the formula describing A 0 , B 0 , and C 0 is
Now consider the region inside all unlabeled half-spaces and outside C and C 0 . The
portion of P within this region can be described by a Karnaugh map [12]:
The '?' appears because four planes cut space into only fifteen regions; since we want a
monotone forces us to make it a '1'. Examining all Peterson-style
formulae on A, B, A 0 , and B 0 reveals that the only formula with this map is
In order to combine the formulae 1, 2, and 3 into a single formula on six variables, we
must determine which operators are repeated in the three formulae. We knew from formulae
1 and 2 that the operators lca f (A; B) and lca f both "and"s-now we know
that they are distinct "and"s because lca f (lca f (A; B); lca f
The "or"s of the first two formulae are distinct because they are descendents of distinct
"and"s. Finally, by Lemma 5.1(3), the "or" of formula 3 is different from the other "or"s
because it is not nested as deeply as the "and"s.
Thus, all five operators of the formula on the six labeled half-spaces appear in the
3. Using the nesting depth of the operators, we know that the formula
looks like (2(2 Filling in the half-space names gives the formula for
the portion of P inside the unlabeled faces:
Notice, however, that in this formula the lca of C and C 0 is an "or". Thus lca f (C; C
"or". But this contradicts Corollary 5.3, so the formula above cannot represent the portion
of P inside the convex hull of P . This contradiction proves that P has no Peterson-style
formula.
6 Closing observations
Though the previous section proves that not all polyhedra have Peterson-style formulae, it
may still be the case that the interior of a polyhedron with n faces can be represented by a
formula using O(n) literals. The trivial upper bound on the size of a formula is O(n 3 ). In
fact, the interiors of any set of cells formed by a collection of n planes can be described by
a formula that represents each convex cell as the "and" of its bounding planes and "or"s
the cell representations together. The size of the formula is at worst the total number of
sides of the cells formed by n planes, which is known to be O(n 3 ) [5].
Recent work by Paterson and Yao improves the upper bound on the size of a formula to
method, like the trivial one, slices the polyhedron into convex polyhedra
by cutting along the planes supporting the faces. By cutting along the planes in a particular
order, and by cutting a subpolyhedron with a plane only when the defining face lies on the
subpolyhedron boundary, the algorithm produces convex pieces whose total number of sides
is O(n 2 ). The formula corresponding to this decomposition has size O(n 2 ).
Neither of the formulae just described is monotone. Every polyhedron does have a
monotone formula, however: For the formula of each cell in the trivial decomposition, we
can "and" all of the half-spaces that contain the cell and then "or" these cell representations.
This formula uses no negations-to see that it defines the polyhedron, notice first that every
point in the polyhedron is in some cell. Second, to move from a cell in the polyhedron to
any point outside the polyhedron you must cross out of a half-space when you first leave
the polyhedron. Thus the representation of an interior cell contains no points outside the
polygon. This implies that the formula evaluates to false at exterior points and shows that
there is a monotone formula with size O(n 4 ).
It would be interesting to characterize the polyhedra that can be represented by Peterson-
style formulae. Peterson [21] showed that the representations of polygons give such formulae
for extrusions and pyramids. We would like to extend this class.
We can also consider looking for formulae for polygons with curved edges. If each edge of
a polygon is a piece of a bi-infinite curve that does not intersect itself, then an edge defines
a half-space with a curved boundary-perhaps we can represent the polygon as a formula
on these half-spaces.
Suppose we restrict the curves so that any two intersect in at most one point (the
pseudoline condition). Then it can be proved that there is always a polygon vertex v such
that the extensions to infinity (through v) of the two edges adjacent to v never intersect
the boundary of the polygon. Since this vertex v can be used as a splitting vertex, such
polygons have Peterson-style formulae.
If the curves are allowed to intersect in more than one point, then it may be impossible
for a formula to represent a polygon without representing other areas of the plane, too. For
example, if two ovals intersect in four points, then the region inside the first oval and outside
the second is disconnected. No boolean formula can represent one connected component
without including the other (unless we are allowed to introduce auxiliary curves).

Acknowledgments

We thank D. P. Peterson and Jorge Stolfi for their helpful discussions and polyhedra. We
also thank Cynthia Hibbard and Mart'in Abadi for their careful reading of the manuscript.



--R

Interactive modeling for design and analysis of solids.

Algorithm Animation.
Computational geometry and convexity.
Algorithms in Combinatorial Geometry
Polygon properties calculated from the vertex neighborhoods.
Finding the convex hull of a simple polygon.
time algorithms for visibility and shortest path problems inside triangulated simple polygons.
A kinetic framework for computational geometry.
Sorting Jordan sequences in linear time.
On finding the convex hull of a simple polygon.
Digital Logic and Computer Design.
An Introduction to Solid Modeling.
A linear algorithm for finding the convex hull of a simple polygon.

Geometric Modeling.
Solid modelling and parametric design in the Medusa system.
Art Gallery Theorems and Algorithms.
Binary partitions with applications to hidden-surface removal and solid modelling
Analysis of set patterns.
Halfspace representation of extrusions
Computational Geometry.
Representations for rigid solids: Theory
Convex hulls of piecewise-smooth Jordan curves
Rational B-splines for curve and surface representation
Convex decomposition of simple polygons.
The PADL-1.0/2 system for defining and displaying solid objects
Graphical input to a Boolean solid modeller.
--TR
Geometric modeling
Computational geometry: an introduction
Algorithms in combinatorial geometry
On-line construction of the convex hull of a simple polyline
Convex hulls of piecewise-smooth Jordan curves
An introduction to solid modeling
Art gallery theorems and algorithms
Polygon properties calculated from the vertex neighborhoods
Sorting Jordan sequences in linear time
Representations for Rigid Solids: Theory, Methods, and Systems
Convex Decomposition of Simple Polygons
Digital Logic and Computer Design

--CTR
Michael S. Paterson , F. Frances Yao, Optimal binary space partitions for orthogonal objects, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.100-106, January 22-24, 1990, San Francisco, California, United States
Marc H. Brown , John Hershberger, Color and Sound in Algorithm Animation, Computer, v.25 n.12, p.52-63, December 1992
M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany
J. Friedman , J. Hershberger , J. Snoeyink, Compliant motion in a simple polygon, Proceedings of the fifth annual symposium on Computational geometry, p.175-186, June 05-07, 1989, Saarbruchen, West Germany
Tamal K. Dey, Triangulation and CSG representation of polyhedra with arbitrary genus, Proceedings of the seventh annual symposium on Computational geometry, p.364-371, June 10-12, 1991, North Conway, New Hampshire, United States
J. Snoeyink , J. Hershberger, Sweeping arrangements of curves, Proceedings of the fifth annual symposium on Computational geometry, p.354-363, June 05-07, 1989, Saarbruchen, West Germany
Michael T. Goodrich, Applying parallel processing techniques to classification problems in constructive solid geometry, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.118-128, January 22-24, 1990, San Francisco, California, United States
boundary-to-CSG conversion algorithms;solid modeling;simple polygons;constructive solid geometry