Call For Papers: Eleventh Annual Symposium on COMPUTATIONAL GEOMETRY

June 5--7, 1995, Vancouver, British Columbia, Canada

Papers, videos and short communications in computational geometry with emphasis on applications with a geometric flavor including robotics, motion planning, computer graphics, solid modeling, computer aided design and manufacturing, pattern recognition, and layout problems are being sought. We welcome submissions that are

algorithmic and combinatorial

including analysis of algorithms and data structures, issues arising from implementations, geometric optimization, analysis of geometric configurations

experimental and applied

including actual implementations with experimental results, comparative studies, real-world applications and their modeling, systems for implementing, debugging or animating geometric algorithms.

Emo Welzl
Freie Universitat Berlin, Institut fur Informatik
Takustr. 9, D-14195 Berlin, Germany
emo@inf.fu-berlin.de

Submissions received past this deadline risk rejection without further consideration. Authors will be notified of acceptance or rejection by January 27, 1995. A copy of each accepted contribution will be due by March 14, 1995, for inclusion in the proceedings. Proceedings will be distributed at the Symposium and will be subsequently available for purchase from ACM. A selection of accepted papers will be invited to special issues of journals; in particular, there will be a special issue on experimental and applied papers.

• Papers must present original research. An extended abstract should begin with a succinct statement of the problems/goals of the paper, the main results, and the significance of the work in the context of previous research. It should provide sufficient detail to allow the program committee to evaluate the validity, quality and relevance of the contribution. The program committee encourages submissions of experimental and applied papers. The entire extended abstract should not exceed 10 double-spaced pages. An optional appendix may be included, but this will be used at the program committee's discretion.
• Communications are limited to two pages and will be published in a separate section of the proceedings. They are primarily meant for reports on experimental results, on experiences with applications of computational geometry in real-world situations and other practical issues that are relevant to computational geometry (but they can also present short notes of algorithmic and combinatorial nature). Communications need not necessarily contain original research, but can be based on research that has already been published elsewhere. They will be presented as posters (possibly with implementation demos) at the conference.
• Video Submissions please consult a separate call for videos. (Authors of videos that are part of a paper should consider also submission to the video section where appropriate.)

Invited Speakers

• Michael Goodchild, Geographical Information Systems
• Pat Hanrahan, Computer Graphics
• David Haussler, Learning Theory

Program Committee

• Mark de Berg (Universiteit Utrecht)
• David Eppstein (UC Irvine)
• Michael Goodrich (Johns Hopkins University)
• Dan Halperin (Stanford University)
• Hiroshi Imai (University of Tokyo)
• Raimund Seidel (UC Berkeley, Univ. des Saarlandes)
• Jack Snoeyink (UBC Vancouver)
• Monique Teillaud (INRIA Sophia Antipolis)
• Seth Teller (Princeton University, MIT)
• Emo Welzl (Freie Universitat Berlin)

Conference Chair: Jack Snoeyink, UBC Vancouver, snoeyink@cs.ubc.ca

The Symposium is sponsored by ACM SIGACT and SIGGRAPH

Addendum to Call for Papers:

Remarks on Experimental and Applied Papers and on Communications

The program committee encourages submissions which report on experimental and applied research. This reflects a general belief in the community, that computational geometry is undergoing a transition from a theoretical field to one in which experimental computation and applications will be more prominent. Such a development should be made visible in the Annual Symposium on Computational Geometry and its proceedings.

Experimental and applied papers submitted to the conference will be evaluated by the same standards as employed in the selection process in previous years. However, the decisions will be based on criteria (with emphasis on relevance) which give experimental and applied papers a fair chance of acceptance.

Authors are advised to prepare their extended abstracts carefully. The presentation of an experiment and its results is a crucial part of the research (at least as crucial as in a more theoretical paper). There should be a clear description of the experimental set-up, the test data used, and the results obtained.

Test data should be chosen carefully, and there should be some justification of why the chosen test set is appropriate. It is desirable to have also test data from applications. This may lead to a deeper understanding of the structure of such data, and/or simply a good collection of examples of such data.

Time performance of an implementation (if this is a result of the experiment) should be reported both in terms of actual time (in seconds, minutes etc.) and in terms of the number of crucial steps in the algorithms. One of the main goals for experimental research in computational geometry is to enhance general knowledge about the actual time complexity of the problems which we consider central to our field (in addition to the quite well developed understanding of the asymptotic step complexity of these problems).

Papers should report on problems arising in their implementations. For example, robustness is a crucial issue. It is of vivid interest to readers to see such problems, and to learn about methods employed to avoid such problems (but even if they cannot be resolved completely, there should be explicit mention of them).

Authors should make it clear whether their implementations and test data will be made public in case of acceptance (via ftp or e-mail). We believe that this is central to a healthy development of experimental science. Authors who for whatever reason will not be able to satisfy this requirement should consider to have their results described in a short communication (see below).

Papers describing applications should contain a thorough study of the requirements and should provide access to test data.

Communications, which are limited to two pages in the submission and in the proceedings, will be presented as posters at the conference. Unless a poster presentation does not seem appropriate for an explicit reason, such a presentation is expected. The main goal of this new section is to broaden the scope of the conference, and to stimulate discussion. Previous publication of the research in journals or proceedings `outside' computational geometry (e.g. at conferences of application areas) does not exclude a communication from acceptance. We hope that references provided to such publications will also encourage the visibility of journals with potential applications in the community.

Authors of accepted papers or accepted communications are encouraged to give software demonstrations of their paper/communication at the conference.

CALL FOR VIDEOS

4th Annual Video Review of Computational Geometry

Videos are sought for a video review of computational geometry.

BACKGROUND:

Computational geometry concepts are often easiest to understand visually. Indeed, most papers in computational geometry rely on diagrams to communicate the intuition behind their results. However, static figures are not always adequate to describe geometric algorithms, since algorithms are inherently dynamic. This video review will showcase advances in the use of algorithm animation, visualization, and interactive computing in the study of computational geometry. In addition, videos which accompany papers submitted to the technical program committee are encouraged.

SUBMISSIONS:

Authors should send one copy of a videotape to the organizer by January 3, 1995. The videotape should be at most five to eight minutes long, and must be in VHS NTSC format for easy reviewing; however, the master tape should be recorded in the best format available to the authors---the final versions of accepted tapes should use a high-quality format.

Each videotape must be accompanied by six (6) copies of a one- or two-page description of the material shown in the video and the techniques used in the implementation. Please format descriptions following the guidelines for ACM proceedings.

Videotapes and accompanying text should be sent to the Video Committee Chair:

David Dobkin Department of Computer Science
Princeton University
Princeton, New Jersey 08544
dpd@cs.princeton.edu

NOTIFICATION:

Authors will be notified of acceptance or rejection by January 27, 1995. For each accepted video, the final version of the textual description will be due by March 14, 1995. The final versions of accepted videos will be due April 18, 1995. The accepted videos will be edited onto one tape, which will be shown at the conference and distributed to conference participants. The video descriptions will be published in the conference proceedings and subsequently be available from ACM.

Video Program Committee

• Nina Amenta (Geometry Center)
• Marc Brown (DEC/SRC)
• David Dobkin (Princeton University)
• D. T. Lee (Northwestern U.)
• Stephen North (ATT Bell Labs)
• Seth Teller (Princeton University, MIT)