.EQ
delim $$
.EN
.LP
.ce 5
\fBThe Computational Geometry Column\fR
\fIJoseph O'Rourke\fR
Department of Computer Science
Johns Hopkins University
Baltimore, MD 21218
.sp
.nh
.PP
Last year a new conference was established under the
joint sponsorship of SIGGRAPH and SIGACT, the
Symposium on Computational Geometry.
At the first symposium, held in June 1985 in Baltimore,
there was some sentiment for starting a SIG.
At the program committee meeting for the second symposium,
however, it was decided to start a \fIComputational
Geometry Column\fR in the two sponsoring organizations'
newsletters instead.  This would satisfy the primary
need for a communication forum without the substantial
overhead of a SIG structure.  This is the first installment
of the column.
.PP
The second symposium was held at IBM Yorktown Heights,
2-4 June 1986.
It attracted 198 participants, 12 more than last year;
54 of the attendees were students.
Statistics provided by the conference chair, Alok Aggarwal of IBM, show that
the conference was dominated by North America, although 10
other countries were represented:
.TS
box center;
l r.
\fICountry\fR	\fINumber\fR
←
United States	139
Canada	28
France	8
Israel	5
West Germany	5
Sweden	4
England	3
Australia	2
Austria	1
Finland	1
Hungary	1
The Netherlands	1
←
Total	198
.TE
A total of 104 papers were submitted, one fewer than last year,
and 34 were accepted.
The division by topic, as determined by the program chair
David Dobkin of Princeton, was as follows.
.TS
box center;
l r r.
\fITopic\fR	\fISubmitted\fR	\fIAccepted\fR
=
Data Structures	13	6
←
Geometric Algorithms	32	14
\ \ \ \ \ Voronoi Diagrams or Hulls	6	2
\ \ \ \ \ Triangulation or Decomposition	10	4
\ \ \ \ \ Visibility	7	4
\ \ \ \ \ Machine Models	3	1
\ \ \ \ \ Other	6	3
←
Motion Planning	13	3
←
Graphics Algorithms	9	2
←
Solid Modeling	13	3
←
Mathematical Bases	12	6
←
Other	5	0
←
Very Late or Withdrawn	7	0	
=
Total	104	34
.TE
David also noticed that this conference represented a
counterexample to the
folk theorem that late papers have
the highest acceptance rate:  in fact the rate was highest
among the first ten received.
.PP
At the risk of insulting the unmentioned, permit me to
offer a personal summary of the technical highlights
of the conference.
The most dramatic advance in the field was presented
the week before at \fISTOC\fR:  Tarjan and Van Wyk
developed a linear-time algorithm for triangulating
a simple polygon.
It has been a long-standing open problem to improve
the several $O(n log n)$ algorithms.
Their algorithm also can determine
whether a polygonal path is simple (non-self-intersecting)
in linear time.
Based on this fundamental triangulation result,
Guibas, Hershberger, Leven, Sharir, and Tarjan were able
to solve several visibility and shortest-path problems
inside simple polygons in linear time.
In particular, they presented an $O(n)$ algorithm for
computing the edge visibility polygon: the region of
a polygon illuminated by a luminescent edge of the
polygon.
Haussler and Welzl introduced a new technique based on
``epsilon-nets," which is in turn based on the
Vapnik-Chervonenkis dimension, which leads to improved
bounds for the fundamental half-space range query
problem.  They achieve $O(n sup alpha )$ query time using
$O(n)$ space, where $alpha$ is smaller than previously
established exponents for all dimensions $d >= 2$.
Guibas and Seidel developed a method of ``reciprocal search"
that enables them to compute the Minkowski sum of two
convex polytopes in three dimensions in time proportional
to the size of the inputs plus the size of the output.
This sum is fundamental for configuration space motion
planning algorithms.
Atallah and Goodrich improved previous parallel algorithms,
achieving $O( log n roman loglog n)$ time
algorithms, with $O(n)$ processors, for several problems
including triangulation of a simple polygon and planar point
location.  The previous best bounds were $O( log sup 2 n)$ time.
D\o'e\''vai showed that hidden line elimination can be
performed in $O(n sup 2 )$ time, which is worst-case optimal,
improving over the many $O(n sup 2 log n)$ algorithms.
The open problem he listed in the proceedings, achieving
the same bound for hidden surface removal, was solved by
McKenna before the conference.  The distinction between the
two problems is that it is easier to determine which edges are visible
in a scene than it is to determine which faces are
visible.  Painting the surfaces requires hidden surface
removal.  Unfortunately, both D\o'e\''vai's and McKenna's
algorithms always use quadratic time, independent of the complexity
of the scene, so their algorithms are unlikely to have direct
practical significance.
Aggarwal, Klawe, Moran, Shor, and Wilber presented an algorithm
for finding all furthest neighbors for the vertices of a convex
polygon in $O(n)$ time, thus settling another long-standing open
problem.  Only $O(n log n)$ algorithms were known previously.
Finally, Fortune presented a novel sweepline algorithm for
constructing the Voronoi diagram, overcoming the apparent necessity
of knowing sites prior to encountering them with the sweepline
by warping the plane.
Although worst-case optimal
algorithms for this problem have been known for a decade,
all are rather complex to implement.  Fortune's algorithm
seems more straightforward, and in addition requires
only $O(n)$ space.
.PP
One result presented on the first day of the conference
was improved by the third:
Wang and Chan showed that the minimum
distance between vertices of two non-intersecting simple
polygons that can see one another can be found in $O(n log n)$
time, and Aggarwal, Moran, Shor, and Suri improved this to $O(n)$
using the same matrix searching algorithm used for the all
furthest neighbors problem.
.PP
Many of the papers presented raised new problems, and
other problems emerged from conversations.  Here are a few
that are open at this writing (another personal list), 
along with their
originator or popularizer or just the person who told me
(I make no attempt to distinguish these cases).
.IP (1)
[Fortune] Compute the three-dimensional Voronoi diagram in
time proportional to the number of cells $k$ in the diagram,
say in $O(n log n + k log n)$ time.  The output size is fixed 
for non-degenerate inputs in
two dimensions but can vary from $OMEGA (n)$ to $OMEGA (n sup 2 )$
in three dimensions.
.IP (2)
[D\o'e\''vai] Perform hidden line elimination (or hidden surface
removal) in time proportional to the number of visible edges
(or surfaces) $k$, say in time $O(n log n + k)$, retaining
$O(n sup 2 )$ performance in the worst case.
.IP (3)
[Aggarwal] Construct the Voronoi diagram of a simple polygon
in linear time.  Techniques similar to that of the Aggarwal, Klawe, Moran, Shor,
and Wilber paper can achieve this for a convex polygon, 
as Aggarwal and Shor have recently shown, but
only $O(n log n)$ algorithms are known for general polygons.
.IP (4)
[Vijayan] Given a planar graph and a sequence of angles between
the adjacent edges incident to each vertex, determine whether
there exists a non-crossing straight line embedding of the graph
that realizes the given angle sequences.  Although special cases
have been solved, it is only known that the general problem is
decidable.
.IP (5)
[Sharir] Determine the number of distinct shortest-path edge
sequences on the surface of a convex polyhedron.
Each such sequence is formed from the labels of the edges crossed
by some path that is the shortest path on the surface between its endpoints.
Sharir established an upper bound of $O(n sup 7 )$, but the best
lower bound is $OMEGA (n sup 2 )$.
.IP (6)
[Lingas] Determine the complexity of finding a minimum length
triangulation of a set of points in the plane.
Although the problem is not known to be NP-hard, no polynomial algorithms
are available, nor are there suboptimal polynomial algorithms
that achieve lengths at most a constant times worse than optimal.
.IP (7)
[Seidel] Can a finite set of non-intersecting lines 
in Euclidean space always be rearranged,
without two lines ever touching during the rearrangement, 
so that
they all become parallel?
.IP (8)
[Many people] Prove or disprove: every non-degenerate (trivalent)
Delaunay triangulation contains a Hamiltonian cycle.
This problem has applications to pattern recognition, which is
where I encountered it several years ago.
(A weaker version occurred to me: show they do or do not have
a perfect matching.)
A nearly equivalent version was discussed extensively at the conference,
particularly among the mathematicians:
does every spherical polytopal graph have a
Hamiltonian cycle?
A polytopal graph is one that may be realized by the vertices and
edges of a three-dimensional convex polytope.
A spherical polytopal graph is one that may be realized by
the vertices and edges of the convex hull of a set of points
on the surface of a sphere (sometimes such graphs are called
inscribable).
It may not be obvious
that there are polytopal graphs that are not spherical, but
indeed there are for much the same reason there are triangulation
graphs that are not Delaunay.  The connection between the two
problems is revealed by the transformations of Brown and of
Edelsbrunner and Seidel between two-dimensional Delaunay
triangulations and three-dimensional convex hulls.
.EQ
delim @@
.EN
.PP
The proceedings of the conference are available from the ACM Order
Department for $19 (members) or $25 (non-members).
The third Symposium on Computational Geometry will be held
in Waterloo, Ontario, 8-10 June 1987.  Derick Wood is the
conference chair, and Chee Yap the program chair.
Extended abstracts are due 15 December 1986.
.PP
Send me your computational geometry news, research announcements,
and open problems for future columns.