Star Unfolding of a Polytope with Applications.
We introduce the notion of a star unfolding of the surface ${\cal P}$ of a three-dimensional convex polytope with n vertices, and use it to solve several problems related to shortest paths on ${\cal P}$.The first algorithm computes the edge sequences traversed by shortest paths on ${\cal P}$ in time $O(n^6 \beta (n) \log n)$, where $\beta (n)$ is an extremely slowly growing function. A much simpler $O(n^6)$ time algorithm that finds a small superset of all such edge sequences is also sketched.The second algorithm is an $O(n^{8}\log n)$ time procedure for computing the geodesic diameter of ${\cal P}$:  the maximum possible separation of two points on ${\cal P}$ with the distance measured along ${\cal P}$.  Finally, we describe an algorithm that preprocesses ${\cal P}$ into a data structure that can efficiently answer the queries of the following form: "Given two points, what is the length of the shortest path connecting them?" Given a parameter $1 \le m \le n^2$, it can preprocess ${\cal P}$ in time $O(n^6 m^{1+\delta})$, for any $\delta > 0$, into a data structure of size $O(n^6m^{1+\delta})$, so that a query can be answered in time $O((\sqrt{n}/m^{1/4}) \log n)$. If one query point always lies on an edge of ${\cal P}$, the algorithm can be improved to use $O(n^5 m^{1+\delta})$ preprocessing time and storage and guarantee $O((n/m)^{1/3} \log n)$ query time for any choice of $m$ between 1 and $n$.
Introduction
The problem of computing shortest paths in Euclidean space amidst polyhedral obstacles arises
in planning optimal collision-free paths for a given robot, and has been widely studied. In two
dimensions, the problem is easy to solve and a number of efficient algorithms have been developed,
see e.g. [SS86, Wel85, Mit93]. However, the problem becomes significantly harder in three dimen-
sions. Canny and Reif [CR87] have shown it to be NP-hard, and the fastest available algorithm
runs in singly-exponential time [RS89, Sha87]. This has motivated researchers to develop efficient
approximation algorithms [Pap85, Cla87] and to study interesting special cases [MMP87, Sha87].
An earlier version of this paper was presented at the Second Scandinavian Workshop on Algorithm Theory
[AAOS90]. Part of the work was carried out when the first two authors were at Courant Institute of Mathematical
Sciences, New York University and later at Dimacs (Center for Discrete Mathematics and Theoretical Computer Sci-
ence), a National Science Foundation Science and Technology Center - NSF-STC88-09648, and the fourth author
was at the Department of Computer Science, The Johns Hopkins University. The work of the first author is supported
by National Science Foundation Grant CCR-91-06514. The work of the second author was also partially supported by
an AT&T Bell Laboratories Ph.D. Scholarship and NSF Grant CCR-92-11541. The third author's work is supported
by NSF grants CCR-88-2194 and CCR-91-22169.
y Computer Science Department, Duke University, Durham, NC 27706 USA
z Computer Science Department, Polytechnic University, Brooklyn, NY 11201 USA
x Department of Computer Science, Smith College, Northampton, MA 01063 USA
- Rm. 3B-412, AT&T Bell Laboratories, 600 Mountain Ave., P.O. Box 636, Murray Hill, NJ 07974 USA
One of the most widely studied special case is computing shortest paths along the surface of a
convex polytope [SS86, MMP87, Mou90]; this problem was originally formulated by H. Dudeney
in 1903; see [Gar61, p. 36]. Sharir and Schorr presented an O(n 3 log n) algorithm for this problem,
which was subsequently improved by Mitchell et al. [MMP87] to O(n 2 log n), and then by Chen
and Han to O(n 2 ) [CH90].
In this paper we consider three problems involving shortest paths on the surface P of a convex
polytope in IR 3 . A shortest path on P is identified uniquely by its endpoints and the sequence
of edges that it encounters. Sharir [Sha87] proved that no more than O(n 7 ) distinct sequences of
edges are actually traversed by the shortest paths on P . This bound was subsequently improved
to \Theta(n 4 ) [Mou85, SO88]. Sharir also gave an O(n 8 log n) time algorithm to compute an O(n 7
superset of shortest-path edge sequences. However computing the exact set of shortest-path edge
sequences seems to be very difficult. Schevon and O'Rourke [SO89] presented an algorithm that
computes the exact set of all shortest-path edge sequences and also identifies, in logarithmic time,
the edge sequences traversed by all shortest paths connecting a given pair of query points lying on
edges of P . The sequences can be explicitly generated, if necessary, in time proportional to their
length. Their algorithm, however, requires O(n 9 log n) time and O(n 8
In this paper we propose two edge-sequence algorithms. The first is a very simple O(n 6 )
algorithm to compute a superset of shortest-path edge sequences, thus improving the result of
[Sha87]; it is described in Section 5. The second computes the exact set of shortest-path edge
sequences in O(n 6 fi(n) log n) time, where fi(:) is an extremely slowly-growing function, a significant
improvement over the previously mentioned O(n 9 log n) algorithm. The computation of the
collection of all shortest-path edge sequences on a polytope is an intermediate step of several algorithms
[Sha87, OS89], and is of interest in its own right.
The second problem studied in this paper is that of computing the geodesic diameter of P ,
i.e., the maximum distance along P between any two points on P . O'Rourke and Schevon [OS89]
gave an O(n 14 log n) time procedure for determining the geodesic diameter of P . In [AAOS90], we
presented a simpler and faster algorithm whose running time is O(n 10 ). An even faster O(n 8 log n)
algorithm is presented in the current version of the paper.
The third problem involves answering queries of the form: "Given x; y 2 P , determine the
distance between x and y along P ." Given a parameter n 2 - s - n 4 , we present a method for
preprocessing P , in O(n 4 s 1+ffi ) time, into a data structure of size O(n 4 s 1+ffi ) for any ffi ? 0, so that
a query can be answered in time O( n
s 1=4 log 2 n). If x is known to lie on an edge of the polytope,
the preprocessing and storage requirements are reduced to O(n 3 s 1+ffi ) and query time becomes
O( n
s 1=3
log 2 n) for
Our algorithms are based on a common geometric concept, the star unfolding. Intuitively, the
star unfolding of P with respect to a point x 2 P can be viewed as follows. Suppose there exists a
unique shortest path from x to every vertex of P . The object obtained after removing these n paths
from P is the star unfolding of P . Remarkably, the resulting set is isometric to a simple planar
polygon and the structure of shortest paths emanating from x on P corresponds to a certain Voronoi
diagram in the plane [AO92]. Together with relative stability of the combinatorial structure of the
unfolding as x moves within a small neighborhood on P , these properties facilitate the construction
of efficient algorithms for the above three problems.
preliminary version of this algorithm [SO88] erroneously claimed a time complexity of O(n 7 2 ff(n) log n); this
claim was corrected in [SO89]. Hwang et al. [HCT89] claimed to have a more efficient procedure for solving the same
problem, but their argument as stated is flawed, and no corrected version has appeared in the literature.
Chen and Han [CH90] have independently discovered the star unfolding and used it for computing
the shortest-path information from a single fixed point on the surface of a polytope. They
however take the unfoldability proven by Aronov and O'Rourke [AO92] for granted.
This paper is organized as follows. In Section 2, we formalize our terminology and list some
basic properties of shortest paths. Section 3 defines the star unfolding and establishes some of its
properties. Section 4 sketches an efficient algorithm to compute a superset of all possible shortest-path
edge sequences, and in Section 5 we present an algorithm for computing the exact set of
sequences; both algorithms are based on the star unfolding. In Section 6 we again use the notion
of star unfolding to obtain a faster algorithm for determining the geodesic diameter of a convex
polytope. Section 7 deals with shortest-path queries. Section 8 contains some concluding remarks
and open problems.
We begin by reviewing the geometry of shortest paths on convex polytopes.
Let P be the surface of a polytope with n vertices. We refer to vertices of P as corners;
the unqualified terms face and edge are reserved for faces and edges of P . We assume that P is
triangulated. This does not change the number of faces and edges of P by more than a multiplicative
constant, but simplifies the description of our algorithms.
2.1 Geodesics and Shortest Paths
A path - on P that cannot be shortened by a local change at any point in its relative interior is
referred to as a geodesic. Equivalently, a geodesic on the surface of a convex polytope is either
a subsegment of an edge or a path that (1) does not pass through corners, though may possibly
terminate at them, (2) is straight near any point in the interior of a face and (3) is transverse to
every edge it meets in such a fashion that it would appear straight if one were to "unfold" the
two faces incident on this edge until they lie in a common plane; see, for example, Sharir and
Schorr [SS86]. The behavior of a geodesic is thus fully determined by its starting point and initial
direction. In the following discussion we disregard the geodesics lying completely within a single
edge of P . Given the sequence of edges a geodesic traverses (i.e., meets) and its starting and ending
points, the geodesic itself can be obtained by laying the faces that it visits out in the plane, so that
adjacent faces share an edge and lie on opposite sides of it, and then connecting the (images of) the
two endpoints by a straight-line segment. In particular, the sequence of traversed edges together
with the endpoints completely determine the geodesic.
Trivially every shortest path along P is a geodesic and no shortest path meets a face or an edge
more than once. We call the length of a shortest path between two points the geodesic
distance between p and q, and denote it by d(p; q). The following additional properties of shortest
paths are crucial for our analysis.
Lemma 2.1 (Sharir and Schorr [SS86]) Let - 1 and - 2 be distinct shortest paths emanating
from x. Let y be a point distinct from x. Then either one of the paths is a subpath of the
other, or neither - 1 nor - 2 can be extended past y while remaining a shortest path. 2
Corollary 2.2 Two shortest paths cross at most once. 2
Lemma 2.3 If - are two distinct shortest paths connecting x; y 2 P, each of the two connected
components of P contains a corner.
Proof: First, Lemma 2.1 implies that removal of splits P into exactly two components. If
one of the two components of contained no corners, - 1 and - 2 would have to traverse
the same sequence of edges and faces. However, there exists at most one geodesic connecting a
given pair of points and traversing a given sequence of edges and faces. 2
2.2 Edge Sequences and Sequence Trees
A shortest-path edge sequence is the sequence of edges intersected by some shortest path - connecting
two points on P , in the order met by -. Such a sequence is maximal if it cannot be extended in
either direction while remaining a shortest-path edge sequence; it is half-maximal if no extension
is possible at one of the two ends. It has been shown by Schevon and O'Rourke [SO88] that the
maximum total number of half-maximal sequences is \Theta(n 3 ).
Observe that every shortest-path edge sequence oe is a prefix of some half-maximal sequence,
namely the one obtained by extending oe maximally at one end. Thus an exhaustive list of O(n 3 )
half-maximal sequences contains, in a sense, all the shortest-path edge-sequence information of P .
More formally, given an arbitrary collection of edge sequences emanating from a fixed edge e, let the
sequence tree \Sigma of this set be the tree with all distinct non-empty prefixes of the given sequences
as nodes, the trivial sequence consisting solely of e as the root, and such that oe is an ancestor
of oe 0 in the tree if and only if oe is prefix of oe 0 [HCT89]. The \Theta(n 3 ) bound on the number of
half-maximal sequences implies that the collection of O(n) sequence trees obtained by considering
all shortest-path edge sequences from each edge of P in turn, has a total of \Theta(n 3 ) leaves and \Theta(n 4 )
nodes in the worst case.
2.3 Ridge Trees and the Source Unfolding
The shortest paths emanating from a fixed source x 2 P cover the surface of P in a way that can
be naturally represented by "unfolding" the paths to a planar layout around x. This unfolding, the
"source unfolding," has been studied since the turn of the century. We will define it precisely in a
moment. A second way to organize the paths in the plane is the "star unfolding," to be defined in
Section 3. This is not quite as natural, and of more recent lineage. Our algorithms will be built
around the star unfolding, but some of the arguments do refer to the source unfolding as well.
Given two points x; y on P , y 2 P is a ridge point with respect to x if there is more than one
shortest path between x and y. Ridge points with respect to x form a ridge tree T x embedded
on P , 2 whose leaves are corners of P , and whose internal vertices have degree at least three and
correspond to points of P with three or more distinct shortest paths to x. In a degenerate situation
where x happens to lie on the ridge tree for some corner p, then p will not be a leaf of T x , but
rather lie internal to T x ; so in general not all corners will appear as leaves of T x . We define a
ridge as a maximal subset of T x consisting of points with exactly two distinct shortest paths to x,
and containing no corners of P . These are the "edges" of T x . Ridges are open geodesics [SS86]; a
stronger characterization of ridges is given in Lemma 2.4. Figs. 1 and 2 show two views of a ridge
tree on a pyramid.
2 For smooth surfaces (Riemannian manifolds), the ridge tree is known as the "cut locus" [Kob67].
A
x

Figure

1: Pyramid, front view: source x, shortest paths to five vertices (solid), ridge tree (dashed).
Coordinates of vertices are (\Sigma1; \Sigma1;
A

Figure

2: Pyramid, side view of Fig. 1. The ridges incident to p 2 and p 4 lie nearly on the edge
We will refer to a point y 2 P as a generic point if it is not a ridge point with respect to any
corner of P . The maximal connected portion of a face (resp. an edge) of P consisting entirely of
generic points will be called a ridge-free region (resp. an edgelet).
x

Figure

3: Ridge-free regions for Fig. 1. T p 1
are shown dashed (e.g., T p 3
is the 'X' on the
bottom face). The ridge-free region containing x is shaded darker.
If we cut P along the ridge tree T x and isometrically embed the resulting set in IR 2 , we obtain
the source unfolding of [OS89]. 3 In the source unfolding, the ridges lie on the boundary of the
unfolding, while x lies at its "center," which results in a star-shaped polygon [SS86]; see Fig. 4. Let
a peel be the closure of a connected component of the set obtained by removing from P both the
ridge tree T x and the shortest paths from x to all corners. A peel is isometric to a convex polygon
[SS86]. Each peel's boundary consists of x, the shortest paths to two corners of P , p and p 0 , and the
unique path in T x connecting p to p 0 . A peel can be thought of as the collection of all the shortest
paths emanating from x between xp and xp 0 . (The peel between xp 1 and xp 5 is shaded in Fig. 4.)
We need to strengthen the characterization of ridges from geodesics to shortest paths, in order
to exploit Corollary 2.2. This characterization seems to be new.
Lemma 2.4 Every ridge of the ridge tree T x , for any point x 2 P, is a shortest path.
Proof: An edge - of the ridge tree is a geodesic consisting of points that have two different shortest
paths to x [SS86]. Suppose - is not a shortest path. Then there must be two points a; b 2 - so
that the portion - 0 of - between a and b is a shortest path, but there is another shortest path, say
connecting them. Refer to Figure 5. By Lemma 2.1, - bg. Let ff 1 and ff 2 be the two
shortest paths from x to a, and fi 1 and fi 2 be the two shortest paths from x to b. Notice that - 0 ,
do not meet except at the endpoints, by Lemma 2.1. In particular, we can relabel
these paths so that the region bounded by (ff as illustrated in the figure, so
that ff 1 and fi 1 approach - 0 "from the same side." There are two cases to consider:
3 The same object is called U(P) in [SS86], "planar layout" in [Mou85], and "outward layout" in [CH90]. For
Riemannian manifolds, it is the "exponential map" [Kob67].
x

Figure

4: Source unfolding for the example in Figs. 1 and 2. Shortest paths to vertices (solid),
polytope edges (dashed), ridges (dotted). One peel is shaded.
x
a 1 a 2
a

Figure

5: Illustration of the proof of Lemma 2.4. Here x is the source, and - a geodesic ridge, with
shortest path. The region \Delta cannot contain any vertices of P .
Case 1: x 62 - 00 . Thus - 00 does not meet ff 1 or ff 2 except at a, by Lemma 2.1. Similarly, - 00 does
not meet fi 1 or fi 2 except at b. Thus, without loss of generality, we can assume that - 00 lies in
the portion \Delta of P bounded by - 0 , ff 1 , and fi 1 , and not containing ff 2 or fi 2 . Now, considering
the source unfolding from x, we observe that \Delta is (isometric to) a triangle contained within
a single peel. \Delta is the area swept by one class of shortest paths from x to y as y ranges over
In particular, \Delta contains no corners. On the other hand, paths are distinct
shortest paths connecting a to b, so by Lemma 2.3 each of the two sets obtained from P by
removing - 0 [- 00 has to contain a corner of P . However, one of these sets is entirely contained
in \Delta-a contradiction.
Case 2: x 2 - 00 . As - 00 and ff 1 can be viewed as emanating from a and having x in common, and
extends past x, Lemma 2.1 implies that ff 1 is a prefix of - 00 . Similarly, ff 2 is a prefix of
contradicting distinctness of ff 1 and ff 2 .Remark. Case 2 in the above proof is vacuous if x is a corner, which is the case in our applications
of this lemma.
As defined, T x is a tree with n vertices of degree less than 3 and thus has \Theta(n) vertices and
edges. However, the worst-case combinatorial size of T x jumps from \Theta(n) to \Theta(n 2 ) if one takes
into account the fact that a ridge is a shortest path comprised of as many as \Theta(n) line segments on
P in the worst case-and it is possible to exhibit a ridge tree for which the number of ridge-edge
incidences is
For simplicity we assume that ridges intersect each edge of P
transversely.
3 Star Unfolding
In this section we introduce the notion of the star unfolding of P and describe its geometric
and combinatorial properties. Working independently, both Chen and Han [CH90] [CH91] and
Rasch [Ras90] have used the same notion, and in fact the idea can be found in Aleksandrov's
work [Ale58, p.226] [AZ67, p.171].
3.1 Geometry of the Star Unfolding
be a generic point, so that there is a unique shortest path connecting x to each corner
of P . These paths are called cuts and are comprised of cut points (see Fig. 1). If P is cut open
along these cuts and embedded isometrically in the plane, then just as with the source unfolding,
the result is a non-self-overlapping simple polygonal region, a two-dimensional complex that we
call the star unfolding S x . That the star unfolding avoids overlap is by no means a straightforward
claim; it was first established in [AO92]:
Lemma 3.1 (Aronov and O'Rourke [AO92]) If viewed as a metric space with the natural definition
of interior metric, S x is isometric to a simple polygon in the plane (with the internal geodesic
metric).
The polygonal boundary @S x consists entirely of edges originating from cuts. The vertices of S x
derive from the corners of P and from the source x. An example is shown in Fig. 6. More complex
A

Figure

Construction of the star unfolding corresponding to Figs. 1 and 2. S x is shaded. The
superimposed dashed edges show the "natural" unfolding obtained by cutting along the four edges
incident to p 3 . The A, B, C, D, and E labels indicate portions of S x derived from those faces; the
relative neighborhood of each x i derives from A.
examples will be shown in Fig. 10.
The cuts partition the faces of P into subfaces, which map to what we call the plates of S x , each
a compact convex polygon with constant number of edges. See Fig. 7. We consider these plates

Figure

7: Plates corresponding to Fig. 6. The square base E is partitioned into two triangles.
to be the faces of the two-dimensional complex S x . We assume that the complex carries with it
labeling information consistent with P .
Somewhat abusing the notation, we will freely switch between viewing S x as a complex and
as a simple polygon embedded in the plane. In particular, a path - ae S x will be referred to as a
segment if it corresponds to a straight-line segment in the planar embedding of S x . Note that every
segment in S x is a shortest path in the intrinsic metric of the complex, but not every shortest path
in S x is a segment, as some shortest paths in S x might bend at corners.
For U(p) be the set of points in S x to which p maps; U is the "unfolding" map (with
respect to x). U(p) is a single point whenever p is not a cut point. is
a set of n distinct points in S x . A non-corner point y 2 P distinct from x and lying on a cut has
exactly two unfolded images in S x . The corners of P map to single points. In particular, we have:
Lemma 3.2 (Sharir and Schorr [SS86]) For a point y 2 P, any shortest path - from x to y
maps to a segment -   ae S x connecting an element of U(y) to an element of U(x). 2
There is a view of S x that relates it to the source unfolding: the star unfolding is just an "inside-
out" version of the source unfolding, in the following sense. The star unfolding can be obtained by
stitching peels together along ridges; see Fig. 8. The source unfolding is obtained by gluing them
along the cuts. Compare with Fig. 4. peel was defined in Section 2.3 as a subset of P , but
slightly abusing the terminology we also use this term to refer to the corresponding set of points
in the source or star unfolding.)
We next define the pasting tree \Pi x as the graph whose nodes are the plates of S x , with two
nodes connected by an arc if the corresponding plates share an edge in S x . See Fig. 9. For a generic

Figure

8: Ridge tree T x ae S x .
point x, \Pi x is a tree with O(n 2 ) nodes, as it is the dual of a convex partition of a simple polygon
without Steiner points. (If x were a ridge point of some corner, S x would not be connected and
\Pi x would be a forest.) \Pi x has only n leaves, corresponding to the triangular plates incident to
the n images of x in S x or, equivalently, to x in P x . By Lemma 3.2, any shortest path from x to
corresponds to a simple path in \Pi x , originating at one of the leaves. Thus, the O(n 3 ) edge
sequences corresponding to the simple paths that originate from leaves of \Pi x include all shortest
path edge sequences emanating from x. In fact, there are O(n 2 ) maximal edge sequences in this
set, one for each pair of leaves.
In the following sections we will need the concept of the "kernel" of a star unfolding. Number
the corners in the order in which cuts emanate from x. Number the n source images
(elements of so that @S is the cycle x comprised of 2n segments (see
Fig. 6). The kernel is a subset of S x , but to define it it would be most convenient to view S x as
embedded in the plane as a simple polygon. Consider the polygonal cycle We claim
that it is the boundary of a simple polygon fully contained in (the embedding of) S x . Indeed,
each line segment
4 is fully contained in the peel sandwiched between x
Thus the line segments p i p i+1 are segments in S x in the sense defined above and indeed form a
simple cycle. The simple n-gon bounded by this cycle is referred to as the kernel K x of the star
unfolding S x . An equivalent way of defining K x is by removing from S x all triangles 4p
Fig. 10 illustrates the star unfolding, and its kernel for several randomly generated
polytopes. 5 Note that neither set is necessarily star-shaped.
We extend the definition of the map U to sets in the natural way by putting
q2Q U(q).
The main property of the kernel that we will need later is:
4 Here are thereafter
5 The unfoldings were produced with code written by Julie DiBiase and Stacia Wyman of Smith College.

Figure

9: Pasting tree \Pi x for Fig. 7: one node per plate.
Lemma 3.3 The image of the ridge tree is completely contained within the kernel, which is itself
a subset of the star unfolding: U(T x
Proof: Since K x can be defined by subtraction from S x , K x ae S x is immediate. The ridge tree
T x can be thought of as the union of the peel boundaries that do not come from cuts. These
boundaries remained when we removed triangles 4p x to form K x (see Fig. 8). 2
Recently Aronov and O'Rourke [AO92] proved that
Theorem 3.4 (Aronov and O'Rourke [AO92]) U(T x ) is exactly the restriction of the planar
Voronoi diagram of the set source images to within K x or, equivalently, to within S x .3.2 Structure of the Star Unfolding
We now describe the combinatorial structure of S x . A vertex of S x is an image of x, of a corner of
P , or of an intersection of an edge of P with a cut. An edge of S x is a maximal portion of an image
of a cut or an edge of P delimited by vertices of S x . It is easy to see that S x consists of \Theta(n 2 )
plates in the worst case, even though its boundary is formed by only 2n segments, the images of
the cuts. We define the combinatorial structure of S x as the 1-skeleton of S x , i.e., the graph whose
nodes and arcs are the vertices and edges of S x , labeled in correspondence with the labels of S x ,
which are in turn derived from labels on P . The combinatorial structure of a star unfolding has
the following crucial property:
Lemma 3.5 Let x and y be two non-corner points lying in the same ridge-free region or on the
same edgelet. Then S x and S y have the same combinatorial structure.

Figure

10: Four star unfoldings: vertices, left to right, top to bottom. The kernel
is shaded darker in each figure.
Proof: Let f be the face containing xy in its interior. The case when xy is part of an edge is
similar.
As the shortest paths from any point z 2 xy to the corners are pairwise disjoint except at z
(cf. Lemma 2.1) and z is confined to f , the combinatorial structure of S z is uniquely determined
by (1) the circular order of the cuts around z, and (2) the sequence of edges and faces of P met by
each of the cuts. We will show that (1) and (2) are invariants of S z as long as z does not cross a
ridge or an edge of P . First, the set of points of f , for which some shortest path to a fixed corner
traverses a fixed edge sequence, is convex-it is simply the intersection of f with the appropriate
peel of the source unfolding with respect to p-implying invariance of (2).
Now suppose the circular order of the cuts around z is not the same for all z 2 xy. The initial
portions of the cuts, as they emanate from any z, cannot coincide, as distinct cuts are disjoint
except at z. Hence there can be a change in this circular order only if one of the vectors pointing
along the initial portion of the cuts changes discontinuously at some intermediate point z
However, this can only happen if z 0 is a ridge point, a contradiction. 2
This lemma holds under more general conditions. Namely, instead of requiring that xy be free
of ridge points, it is sufficient to assume that the number of distinct shortest paths connecting z to
any corner does not change as z varies along xy.
Lemma 3.6 Under the assumptions of Lemma 3.5, K x is isometric to K y , i.e., they are congruent
simple polygons.
Proof: K x is determined by the order of corners on @K for each i, by the
choice of the shortest path p i p i+1 , if there are two or more such paths. The ordering is fixed, once
combinatorial structure of S x is determined. The choice of the shortest path connecting p i to p i+1
is determined by the constraint that 4p
Let R be a ridge-free region. By the above lemma, S x can be embedded in the plane in such a
way that the images of the corners of P are fixed for all x 2 R, and the images of x in S x move as
x varies in R ' P . This guarantees that K This is illustrated in Fig. 11. In
what follows, we are going to assume such an embedding of S x , and use KR to denote K x for all
points x 2 R. Similarly, define K " for an edgelet ".
3.3 How Many Different Unfoldings Are There?
For the algorithms described in this paper, it will be important to bound the number of different
possible combinatorial structures of star unfoldings, as we vary the position of source point x, and
to efficiently compute these unfoldings (more precisely, compute their combinatorial structure plus
some metric description, parametrized by the exact position of the source), as the source moves on
the surface of the polytope. Two variants of this problem will be needed. In the first, we assume
that the source is placed on an edge of P , and in the second the source is placed anywhere on P .
In view of Lemma 3.5, it suffices to bound the number of edgelets and ridge-free regions.
Lemma 3.7 In the worst case, there are \Theta(n 3 ) edgelets and they can be computed in O(n 3 log n)
time.
Proof: Each edge can meet a ridge of the ridge tree of a corner at most once, since ridges are
shortest paths (recall that we assume that no ridge overlaps an edge-removal of this assumption
does not invalidate our argument, but only adds a number of technical complications). This gives

Figure

11: The star unfolding when the source x moves to y inside a ridge-free region. The unfolding
shown lightly shaded; S y is shown dotted. Their common kernel K y is the
central dark region.
an upper bound of n \Theta O(n) \Theta O(n) on the number of edge-ridge intersections and therefore on the
number of edgelets. An example
are present is relatively easy to construct
by modifying the lower bound construction of Mount [Mou90].
To compute the edgelets, we construct ridge trees from every corner in n \Theta O(n 2
applications of the algorithm of Chen and Han [CH90]. The edgelets are now computed by sorting
the intersections of ridges along each edge. 2
Lemma 3.8 In the worst case, there are \Theta(n 4 ) ridge-free regions on P. They can be computed in
Proof: The overlay of n ridge trees, one from each corner of P , produces a subdivision of P in
which every region is bounded by at least three edges. Thus, by Euler's formula, the number
of regions in this subdivision is proportional to the number of its vertices, which we proceed to
estimate.
By Lemma 2.4 ridges are shortest paths and therefore two of them intersect in at most two
points (cf. Corollary 2.2) or overlap. In the latter case no new vertex of the subdivision is created,
so we restrict our attention to the former. In particular, as there are n \Theta ridges, the
total number of their intersection points is O(n 4 ). Refining this partition further by adding the
edges of P does not affect the asymptotic complexity of the partition, as ridges intersect edges in
O(n 3 ) points altogether. This establishes the upper bound.
It is easily checked that in Mount's example of a polytope
there
regions. Hence there are \Theta(n 4 ) ridge-free regions on P
in the worst case.
The ridge-free regions can be computed by calculating the ridge tree for every corner, and
overlaying the trees in each face of P . The first step takes O(n 3 ) time, while the second step
can be accomplished in time O((r r is the number of ridge-free
regions in P , using the line-sweep algorithm of Bentley and Ottmann [BO79]. If computing the
ridge-free regions is a bottleneck, the last step can be improved to O(n 4 ) by using a significantly
more complicated algorithm of Chazelle and Edelsbrunner [CE92]. 2
3.4 How Many Different Ridge Trees Are There?
In Section 3.1, we proved that the combinatorial structure of S x is the same for all points x in a
ridge-free region. As x moves in a ridge-free region, the ridge tree T x changes continuously, as a
subset of P . In this subsection, we prove an upper bound on the number of different combinatorial
structures of T x as the source point x varies over a ridge-free region or an edgelet. Apart from being
interesting in their own right, we need these results in the algorithms described in Sections 5-7.
Let R be a ridge-free region, and let x be a point in R. By Theorem 3.4, T x is the Voronoi
diagram V x of clipped to lie within KR . Since ridge vertices do not lie on @S x , all
changes in T x , as x varies in R, can be attributed to changes in V x . Thus it suffices to count the
number of different combinatorial structures of Voronoi diagrams V x , x 2 R.
g. For each x
are the coordinates of a generic point y in the plane. Let
the lower envelope of the f i 's. Then V x is the same as (the 1-skeleton of) the orthogonal projection
of the graph of f(y) onto the y 1 y 2 -plane.
We introduce an orthogonal coordinate system in R and let x have coordinates (s; t) in this
system. Then positions of x i are linear functions of s; t of the form
x i2
' a i
where (a are coordinates of x i when x is at the origin of the (s; t) coordinate system in R, and
defines the orientation of the ith image of R in the plane.
We now regard f and f i 's as 4-variate functions of s; t; y by MR the projection
of the graph of f onto the (s; t; y It can be shown that total number of different
combinatorial structures of V x is bounded by the number of faces in MR . Let
Using (1) we obtain
where, for each i, the C i 's are constants that depend solely on a
denote the lower envelope of the g i 's. Since g(s; t; y
the projection of the graph of g is the same as MR . Let
and set
Then every face of the graph of g is the intersection of the lower envelope of -
's with the surface
defined by the equations (3). Since each - g i is a 8-variate linear function, by the Upper Bound
Theorem for convex polyhedra, the graph of their lower envelope has O(n 4 ) faces. Hence, the
number of faces in MR is also O(n 4 ). Using the algorithm of Chazelle [C91], all the faces of this
lower envelope and thus also those of MR can be computed in O(n 4 ) time. Putting everything
together, we conclude
Lemma 3.9 The total number of different combinatorial structures of ridge trees for source points
lying in a ridge-free region R is O(n 4 ). Moreover, the faces of MR can be computed in time O(n 4 ).
Remark. The only reason for assuming in the above analysis that x stays away from the boundary
of R was to ensure that the vertices of the Voronoi diagram avoid the boundary of KR . However,
it is easy to verify that when x is allowed to vary over the closure of R, Voronoi vertices never cross
the boundary of KR , but may touch it in limiting configurations. Thus the same analysis applies
in that case as well.
An immediate corollary of the above lemma and Lemma 3.8 is
Corollary 3.10 The total number of different combinatorial structures of ridge trees for a convex
polytope in IR 3 with n vertices is O(n 8 ).
If the source point moves along an edgelet " rather in a ridge-free region, we can obtain a
bound on the number of different combinatorial structures of ridge trees by setting
Proceeding in the same way as above, each g i now becomes
We now define the subdivision M " as the projection of the graph of the lower envelope of g i 's. Let
i is now a 5-variate linear function, by the Upper Bound Theorem, the number of faces in
" is O(n 3 ), which implies that there are O(n 3 ) distinct combinatorial structures of ridge trees as
x varies along ". Moreover, M " can be computed in time O(n 3 ) [C91]. Hence, we obtain
Lemma 3.11 The total number of distinct ridge trees as the source point moves in an edgelet is
O(n 3 ), and the subdivision M " can be computed in O(n 3 ) time.
Remarks. (i) None of Lemma 3.9, Corollary 3.10, or Lemma 3.11 are known to be tight.
(ii) In the above analysis for MR (resp. M " ) the only portion of the structure that is relevant
for our algorithms is that which corresponds to points with (s;
We will have to "filter out" irrelevant features at a later stage in the
computation.
4 Edge Sequences Superset
In this section we describe an O(n 6 ) algorithm for constructing a superset of the shortest-path
edge sequences, which is both more efficient and conceptually simpler than previously suggested
procedures, and which produces a smaller set of sequences.
Observe that all shortest-path edge sequences are realized by pairs of points lying on edges
of P-any other shortest path can be contracted without affecting its edge sequence so that its
endpoints lie on edges of P . Let x be a generic point lying on an edgelet ". As mentioned in
Section 3.1, the pasting tree \Pi x contains all shortest path edge sequences that emanate from x.
Moreover by Lemma 3.5, \Pi x is independent of choice of x in ". Therefore, the set of O(n 3 ) pasting
trees is an edgeletg, each of size O(n 2 ), contains an implicit representation of a
set of O(n 6 ) sequences (O(n 5 ) of which are maximal in this set), which includes all shortest-path
edge sequences that emanate from generic points.
Algorithm 1: Sequence Trees
for each edge e of P do
for each edgelet endpoint v 2 e do
Compute shortest-path edge sequences \Sigma v emanating from v.
for each edgelet " ae e do
Choose a point x 2 ".
Compute
for each maximal sequence oe 2 \Pi x do
for each sequence oe 2 \Sigma e do
Traverse oe, augmenting T e .
Stop if oe visits the same edge twice.
T e is the sequence tree containing shortest path edge sequences
emanating from e.
Hence, we can compute a superset of shortest path edge sequences in three steps: First, partition
each edge of P into O(n 3 ) edgelets in time O(n 3 ) as described in Lemma 3.7. Second, compute
shortest path edge sequences from the endpoints of each edgelet, using Chen and Han's shortest path
algorithm. Next, compute the star unfolding from a point in each edgelet, again using the shortest
path algorithm. The total time spent in the last two steps is O(n 5 ). Finally, this representation of
edge sequences is transformed into O(n) sequence trees, one for each edge (cf. Section 2.2) in time
O(n 6 ) in a straightforward manner; see Algorithm 1 for the pseudocode. We thus obtain
Theorem 4.1 Given a convex polytope in IR 3 with n vertices, one can construct, in time O(n 6 ),
O(n) sequence trees that store a set of O(n 6 ) edge sequences, which include all shortest path edge
sequences of P. 2
Remark. (i) Note that our algorithm uses nothing more complex than the algorithm of Chen
and Han for computing shortest paths from a fixed point, plus some sorting and tree traversals. It
achieves an improvement over previous algorithms mainly by reorganizing the computation around
the star unfolding.
(ii) The sequence-tree representation for just the shortest-path edge sequences is smaller by a
factor of n 2 than our estimate on the size of the set produced by Algorithm 1 (cf. Section 2.2), but
computing it efficiently seems difficult. In addition, it is not clear how far the actual output of our
algorithm is from the set of all shortest-path edge sequences. We have a sketch of a construction for
a class of polytopes that force our algorithm to
sequences.
5 Exact Set of Shortest-Path Edge Sequences
In this section, we present an O(n 3 fi(n) log n) algorithm, for computing the exact set of maximal
shortest-path edge sequences emanating from an edgelet. Here fi(\Delta) is an extremely slowly growing
asymptotically smaller than log   n. Running this algorithm for all edgelets of P , the exact
set of maximal shortest-path edge sequences can be computed in time O(n 6 fi(n) log n), which is a
significant improvement over Schevon and O'Rourke's O(n 9 log n) algorithm [SO89].
" be an edgelet. We are interested in computing maximal shortest-path edge sequences
(corresponding to paths) emanating from x, for all x 2 ". For each fixed x, the shortest paths
originating from x can be subdivided according to their initial direction. If the path leaves x
between xp i\Gamma1 and xp i , it corresponds to a segment in S x emanating from x i , the ith image of x.
The area swept by all such segments, for a fixed x and i, is exactly the ith peel. Let us concentrate
on the portion P x;i of the ith peel that lies in K One measure of how far the 'influence' of
extends into K " , as x moves along ", is the union C
x2" P x;i . C i is the union of a family of
convex sets P x;i sharing p as a boundary edge, therefore C i is star-shaped with respect to any
point z 2 p It is easily checked that the restriction of a plate of S x to
not vary with x 2 ". It therefore makes sense to talk about the nodes of \Pi x visited
by fl i . We say that visits a node v of \Pi x if fl i intersects the plate corresponding to v.
Observe that every maximal (over all x in ") edge sequence corresponding to a shortest path
emanating from x between xp i\Gamma1 and xp i is realized by some shortest path that connects x i to some
point y on in fact to a ridge vertex of P x;i . This sequence is determined solely by the plate
of \Pi x that contains y. Hence, it is sufficient to determine the furthest that fl i gets from x i in \Pi x .
More formally, consider the minimal subtree \Pi x;i of \Pi x rooted at (the plate incident to) x i and
containing all nodes of \Pi x visited by fl i . The paths from the root of \Pi x;i to its leaves correspond to
desired maximal sequences. Repeating this procedure for all images x i , we can collect all maximal
sequences corresponding to shortest paths from points on ".
The above idea can be made algorithmic, but transforming it directly to an algorithm requires
computing the sets C i (i.e., taking the union of a continuous family of convex sets P x;i , each
obtained by deleting 4p from the ith peel), which is rather intricate. We therefore use a
shortcut, replacing fl i by an easier-to-compute curve fl 0
. Since the desired maximal sequences are
necessarily realized by shortest paths from x i to one of the ridge vertices lying on @P x;i , we only
need to consider the portion of fl i that contains a vertex of T x , for some x 2 ". We now show how
to compute a curve fl 0
i that contains this portion of fl i .
A generic ridge vertex v is incident to three open peels c has degree more than
four and exists at more than just a discrete set of positions of x 2 ", we arbitrarily pick a triple
of open peels to define it. As x moves along ", the vertex traces an algebraic curve
in K x . Let a lifetime of a ridge vertex v, defined by c , be a maximal connected interval
implies that v is a vertex of T x . Let \Gamma i be the set of curves traced out
by ridge vertices that appear on the boundary of P x;i during their lifetimes; set n j. It can
be verified that the arcs in \Gamma i are the projections of those edges of the subdivision M " , defined in
Section 3.4, at which g i appears on the lower envelope of g i 's. (As we mentioned in Section 3.4,
may contain "irrelevant" features. In particular, we must truncate each aforementioned arc
so that it corresponds to positions of the source on ". Secondly, we must verify that the Voronoi
diagram vertex corresponding to the arc indeed yields a ridge vertex. It is sufficient to check, for
a single point of the curve traced out by the vertex as x ranges over ", that it lies inside K " , as
a ridge vertex cannot leave K " . This is easily accomplished by one point-location query per arc.)
Therefore, by Lemma 3.11,
summation is taken over all peels of S x , and all
can be computed in time O(n 3 ).
Let z be a point on p . If we introduce polar coordinates with z as the origin, each arc
can be regarded as a univariate function constant number of '-
monotone arcs if is not '-monotone; this is possible since g i is a portion of an algebraic curve of
small degree). Let fl 00
i be the graph of the upper envelope of arcs in \Gamma i . Since fl i is a portion of
the boundary of a set star-shaped with respect to z, the portion of fl i that contains a vertex of
the ridge tree T x , for some x 2 ", lies on fl 00
i . However, fl 00
i is not necessarily a connected arc.
Suppose are the endpoints of the connected components of fl 0
counterclockwise direction around z; we connect u 2i to u 2i+1 by a segment for each m. The
resulting curve is the desired curve fl 0
i is a piecewise algebraic '-monotone arc. Since each arc
i , has O(n i fi(n i
is a constant depending on the maximum degree of arcs in \Gamma i , and ff(\Delta) is the inverse Ackermann
function. Using a divide-and-conquer approach fl 00
i can be computed in time O(n
[HS86].
We now trace fl 0
lies in the portion K " [z] of K " visible from z.
Compute this portion, in linear time [EA81], and subdivide K " [z] into a linear number of triangles
all incident to z. Now partition fl 0
into connected portions each fully contained in one
of these triangles. This can be done in time proportional to the number of arcs constituting fl 0
and the number of triangles involved and produces at most O(n) extra arcs, as
i is '-monotone
and thus crosses each segment separating consecutive triangles in at most one point. Since each
triangle 4 is fully contained in K " and thus encloses no images of a vertex of P , the set of plates
of S x met by 4 corresponds to a subtree \Pi 4 of \Pi x of linear size, with at most one vertex of degree
3 and all remaining vertices of degree at most 2. Hence, \Pi 4 can be covered by two simple paths
and they can be computed in linear time. For each - j ae 4, we determine the
furthest node that - i reaches in \Pi 1
4 by binary search. An intersection between - j and a plate
of K " can be detected in O(1) time, so the binary search requires only O(log n) time. The total
time spent is thus O(n i fi(n) log n triangles of K " [z], and O(n 3 fi(n) log n) over all
The above processing is repeated for each of the O(n 3 ) edgelets ". This completes the description
of the algorithm. It is summarized in Algorithm 2.
Algorithm 2: Exact Edge Sequences
edgelets.
for each edgelet " do
of projections of edges in M " .
Eliminate irrelevant features from \Gamma.
for each image x i do
of \Gamma at which g i appears on the lower envelope.
Compute upper envelope fl 00
Convert
into a connected arc
Compute
for each 4 in the triangulation do
Compute
Compute
Compute
4 .
Find subtrees of \Pi 1
4 visited by fl 4 .
Theorem 5.1 The exact set of all shortest-path edge sequences on the surface of a 3-polytope on
n vertices can be computed in O(n 6 fi(n) log n) time, where n) is an extremely slowly
growing function.
6 Geodesic Diameter
In this section we present an O(n 8 log n) time algorithm to determine the geodesic diameter of P . As
mentioned in the introduction, this question was first investigated by O'Rourke and Schevon [OS89]
who presented an O(n 14 log n) time algorithm for computing it. Their algorithm relies on the
following observation:
Lemma 6.1 (O'Rourke and Schevon [OS89]) If a pair of points x; y 2 P realizes the diameter
of P, then either x or y is a corner of P, or there are at least five distinct shortest paths between
x and y. 2
Lemma 6.1 suggests the following strategy for locating all diametral pairs. We first dispose of
the possibility that either x or y is a corner in n \Theta O(n 2 just as in [OS89]. Next,
we fix a ridge-free region R and let MR be the subdivision defined in Section 3.4. We need to
compute all pairs of points x 2 cl (R) and y   2 K x such that there are at least five distinct shortest
paths between x and y, with . By a result of Schevon [Sch89], such a pair x; y can be a
diametral pair only if it is the only pair, in a sufficiently small neighborhood of x and y, with at
least five distinct shortest paths between them. Such a pair of points corresponds to a vertex of
MR . Hence, we use the following approach.
We first compute, in O(n 4 ) time, all ridge-free regions of P (cf. Lemma 3.8). Next, for each
ridge-free region R, we compute KR , vertices of MR , and f(v) for all vertices of MR (recall that
f(v) is the shortest distance from v to any source image; cf. Section 3.3). Next, for each vertex
lies in the closure of R and (y 1
the answer of both of these questions is 'yes', we add v to the list of candidates for diametral pairs.
(This step is exactly the elimination of "irrelevant features" mentioned at the end of Section 3.4.
Once the two conditions are verified, we know that f(v) is exactly d(x; y).)
Finally, among all diametral candidate pairs, we choose a pair that has the largest geodesic
distance. See Algorithm 3 for the pseudocode.
For each ridge-free region R, KR can be computed in time O(n 2 ) and preprocessed for planar
point location in additional O(n log n) time using the algorithm of Sarnak and Tarjan [ST86]. By
Lemma 3.9, vertices of MR and f(v), for all vertices of MR , can be computed in time O(n 4 ). We
spend O(log n) time for point location at each vertex of MR , so the total time spent is O(n 8 log n).
Algorithm 3: Geodesic Diameter
for each corner c of P do
Construct the ridge tree T c with respect to c.
for each vertex v of T c do
Add d(c; v) to the list of diameter candidates.
Compute the ridge-free regions.
for each ridge-free region R do
Compute MR and f(v) for all vertices v 2 MR .
Compute
Construct
Preprocess KR for point location queries.
Preprocess cl (R) for point location queries.
for each vertex of MR do
cl (R) and (y 1
to the list of diameter candidates.
Find a diametral candidate pair with the maximum geodesic distance.
Theorem 6.2 The geodesic diameter of a convex polytope in IR 3 with a total of n vertices can be
computed in time O(n 8 log n).
7 Shortest-Path Queries
In this section we discuss the preprocessing needed to support queries of the form: "Given x; y 2 P ,
determine d(x; y)". We assume that each point is given together with the face (or the edge) of P
containing it. Two variants of the problem are considered: (1) no assumption is made about x and
y and (2) x is assumed to lie on an edge of P .
Our data structure is based on the following observations. Let x; y be two query points. Suppose
is a generic point lying in a ridge-free region R and y  is an image of y in S x .
If y   2 KR , then
On the other hand, if y   62 K x , then it lies in one of the triangles 4p
denotes the Euclidean length of a line segment in (the planar embedding) of 4p
We thus need a data structure that, given a point y, can determine whether
Let -R denote the preimage of @KR on P , so U(-R partitions each face f of P into
convex regions. By the nature of the way f is partitioned by -R , the regions in f can be linearly
ordered (i.e., their adjacency graph is a chain), so that determining the region of f containing a
given point y 2 f can be done in logarithmic time by binary search. Let \Delta ' f be such a region,
then either U (\Delta) ' KR or U (\Delta) " In fact, one can prove a more interesting property of
\Delta.
Lemma 7.1 Let R be a ridge-free region or an edgelet, let f be a face of P, and let \Delta be a connected
component of f n -R whose image is not contained in KR . Then the sequence of edges traversed by
the shortest path -(x; y) is independent of the choice of x 2 R and y 2 \Delta.
Proof: For the sake of a contradiction, suppose there are two points such that the
sequences of edges traversed by -(x; y 0 ) and -(x; y 00 ) are distinct. Then there must exist a point
with two shortest paths to x-to obtain such a point, move y from one end of y 0 y 00 to
the other and observe that the shortest path from x to y changes continuously and maintains the
set of edges of P that it meets, except at points y with more than one shortest path to x. Thus
. However, the segment y 0 y 00 ae \Delta as \Delta is convex, implying
Similarly, if x are such that the paths connecting these two points to y 2 \Delta traverse
different edge sequences, there must exist x 2 x 0 x 00 which is connected to y by two shortest paths,
again forcing y onto T x and yielding a contradiction. The lemma follows easily. 2
This lemma suggests the following approach to computing d(x; y) for U(y) not contained in
KR . For each connected component \Delta in f n -R , whose image is not contained in KR , one can
precompute the edge sequence for shortest paths from a point in R to a point in \Delta. This in
turn determines the transformation of coordinates from the f-based coordinates to the coordinates
usable in the planar unfolding of S x -thus we may now compute an image y   of y and the peel
of S x that contains y   under this unfolding map, which as noted above immediately yields d(x; y).
Hence, we can preprocess P in time O(n 2 log n) into a data structure of size O(n 2 ), so that one can
determine in O(log n) time whether U(y) 2 K x and, if U(y) 62 K x , then it also returns d(x; y) in
additional constant time.
Next assume that U(y) ae KR . Note that the data structure just described can be used to
compute the coordinates of U(y) even if U(y) ae KR . Now one has to compute
1-i-n
are the same as in (3). Let H be the set of hyperplanes in IR 9 corresponding to the
graphs of - g i 's, i.e.,
Then computing the value of g(s; t; y is the same as determining the first hyperplane of H
intersected by the vertical ray emanating from the point (s; t; y in the
positive v 5 -direction. Agarwal and Matou-sek [AM92] have described a data structure that, given a
set G of n hyperplanes in IR d and a parameter n - s - n bd=2c , can preprocess G, in time O(s 1+ffi ),
into a data structure of size O(s 1+ffi ), so that the first hyperplane of G intersected by a vertical ray
emanating from a point with x can be computed in time O( n
s 1=bd=2c
log 2 n). Since
in our case, we obtain a data structure of size O(s 1+ffi ) so that a query can be answered in time
O( n
s 1=4
log 2 n).
As described in Lemma 3.8, one can partition all faces of P into ridge-free regions in time O(n 4 ).
For each ridge-free region, we construct the above data structures. Finally, if x is not a generic
point then, as mentioned in the remark following Lemma 3.9, we can use the data structures of any
of the ridge-free regions whose boundaries contain x. It is easy to see by a continuity argument
that all shortest paths from such a point are encoded equally well in the data structures of all the
ridge-tree regions touching x.
In summary, for a pair of points x; y 2 P , d(x; y) is computed in the following three steps. We
assume that we are given the faces f x ; f y containing x; y, respectively. First find in O(log n) time
the ridge-free region R of f x whose closure contains x. Next find in O(log n) time the region \Delta of
f y n-R that contains y. If \Delta does not lie in KR , using the information stored at \Delta, compute d(x; y).
(The data structure required for handling this case has size \Theta(n 2 ) per ridge-free region in the worst
case. Hence choosing does not produce asymptotic space savings while reducing query
time.) Otherwise, compute d(x; y) in time O( n
s 1=4
log 2 n) using the vertical ray shooting structure.
Hence, we can conclude
Theorem 7.2 Given a polytope P in IR 3 with n vertices and a parameter n 2 - s - n 4 , one can
construct, in time O(n 4 s 1+ffi ) for any ffi ? 0, a data structure of size O(n 4 s 1+ffi ), so that d(x; y) for
any two points x; y 2 P can be computed in time O( n
s 1=4 log 2 n).
If x always lies on an edge, then H is a set of hyperplanes in IR 6 , so the query time of the
vertical ray shooting data structure is now O( n
s 1=3 log 2 n) for Moreover, we have to
construct only O(n 3 ) different data structures, one for each edgelet, so we can conclude
Theorem 7.3 Given a polytope P in IR 3 with n vertices and a parameter n 2 - s - n 3 , one can
construct in time, O(n 3 s 1+ffi ) for any ffi ? 0, a data structure of size O(n 3 s 1+ffi ), so that for any two
points x; y 2 P such that x lies on an edge of P one can compute d(x; y) in time O( n
s 1=3
log 2 n).
Remark. The performance can be slightly improved by employing the algorithm of Matou-sek and
Schwarzkopf [MS93].
8 Discussion and Open Problems
We have shown that use of the star unfolding of a polytope leads to substantial improvements
in the time complexity of three problems related to shortest paths on the surface of a convex
polytope: finding edge sequences, computing the geodesic diameter, and distance queries. Moreover,
the algorithms are not only theoretical improvements, but also, we believe, significant conceptual
simplifications. This demonstrates the utility of the star unfolding.
We conclude by mentioning some open problems
1. Can one obtain a better upper bound on the number of different combinatorial structures
of ridge trees by using a more global argument? Such an improvement will yield a similar
improvement in the time complexities of diameter and exact shortest path edge sequences
algorithms.
2. Can one answer answer a shortest path query faster if both x and y lie on some edge of
P? This special case is important for planning paths among convex polyhedra (see Sharir
[Sha87]).



--R

Star unfolding of a polytope with applications.
Konvexe Polyeder.
Ray shooting and parametric search.
Nonoverlap of the star unfolding.
Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
Intrinsic Geometry of Surfaces.
Algorithms for reporting and counting geometric intersections.
New lower bound techniques for robot motion planning problems.
An optimal convex hull algorithm for point sets in any fixed dimension.
An optimal algorithm for intersecting line segments in the plane.
Shortest paths on a polyhedron.
Storing shortest paths for a polyhedron.
Approximate algorithms for shortest path motion planning.
A linear algorithm for computing the visibility polygon from a point.
The 2nd Scientific AMerican Book of Mathematical Puzzles and Diversions
Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
Finding all shortest path edge sequences on a convex polyhedron.
On conjugate and cut loci.
On finding shortest paths on convex polyhedra.
Shortest paths among obstacles in the plane.
The discrete geodesic problem.
The number of shortest paths on the surface of a polyhedron.

Computing the geodesic diameter of a 3-polytope
An algorithm for shortest paths motion in three dimensions
Shortest paths along a convex polyhedron.
Shortest paths in Euclidean space with polyhedral obstacles
Algorithms for geodesics on polytopes.
A convex hull algorithm optimal for point sets in even dimensions.
On shortest paths amidst convex polyhedra.
The number of maximal edge sequences on a convex poly- tope
An algorithm for finding edge sequences on a polytope.
On shortest paths in polyhedral spaces.
Planar point location using persistent search trees.
Constructing the visibility graph for n line segments in O(n 2
--TR

--CTR
Sariel Har-Peled, Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.359-365, June 04-06, 1997, Nice, France
Yi-Jen Chiang , Joseph S. B. Mitchell, Two-point Euclidean shortest path queries in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.215-224, January 17-19, 1999, Baltimore, Maryland, United States
Marshall Bern , Erik D. Demaine , David Eppstein , Eric Kuo , Andrea Mantler , Jack Snoeyink, Ununfoldable polyhedra with convex faces, Computational Geometry: Theory and Applications, v.24 n.2, p.51-62, February
Mark Lanthier , Anil Maheshwari , Jrg-Rdiger Sack, Approximating weighted shortest paths on polyhedral surfaces, Proceedings of the thirteenth annual symposium on Computational geometry, p.485-486, June 04-06, 1997, Nice, France
Mark Lanthier , Anil Maheshwari , Jrg-Rdiger Sack, Approximating weighted shortest paths on polyhedral surfaces, Proceedings of the thirteenth annual symposium on Computational geometry, p.274-283, June 04-06, 1997, Nice, France
Demaine , Martin Demaine , Anna Lubiw , Joseph O'Rourke , Irena Pashchenko, Metamorphosis of the cube, Proceedings of the fifteenth annual symposium on Computational geometry, p.409-410, June 13-16, 1999, Miami Beach, Florida, United States
geodesics;shortest paths;star unfolding;convex polytopes