Last year a new conference, the Symposium on Computational Geometry, was established under the joint sponsorship of SIGGRAPH and SIGACT. 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 Computational Geometry Column 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.

The second symposium was held at IBM Yorktown Heights, June 24, 1986. It attracted 198 participants, 12 more than in 1985; 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:

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:

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 10 received.

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 STOC: 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 logn) 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(na) query time using O(n) space, where a is smaller than previously established exponents for all dimensions d e 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(logn loglogn) 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(log2n) time. Devai showed that hidden line elimination can be performed in O(n2) time, which is worst-case optimal, improving over the many O(n2 logn) 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 Devai'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 logn) 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.

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 logn) 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.

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).

The proceedings of the second Symposium on Computational Geometry are available from the ACM Order Department, P. O. Box 64145, Baltimore, MD 21264, order no. 429860, for $19 (members) or $25 (non-members). The third Symposium on Computational Geometry will be held in Waterloo, Ontario, June 810, 1987. Derick Wood is the conference chair and Chee Yap is the program chair. Extended abstracts are due December 15, 1986.

Send me your computational geometry news, research announcements and open problems for future columns.