Papers and Communications accepted to the 13th Annual ACM Symposium on Computational Geometry, June 4-6 1997, Nice, France

Regular Papers

Applied Track

1. Halperin, Shelton. A perturbation scheme for spherical arrangements with application to molecular modeling.
2. Attali. R-regular shape reconstruction from unorganized points.
3. Mitchell. Choosing corners of rectangles for mapped meshing.
4. Finn, Kavaraki, Latombe, Motwani, Shelton, Venkatasubramanian, Yao. RAPID: randomized pharmacophore identification for drug design.
5. Milenkovic. Rotational polygon overlap minimization.
6. Berg, Bose, Cheng, Halperin, Matousek, Schwarzkopf. New results on casting.
7. Mata, Mitchell. A new algorithm for computing the shortest paths in planar subdivisions.
8. Barequet, Kaplan. A data front end for layered manufacturing.
9. Bronnimann, Yvinec. Efficient exact evaluation of signs of determinants.
10. Bronnimann, Emiris, Pan, Pion. Computing exact geometric predicates using modular arithmetic with single precision
11. Boissonnnat, de Lange, Teillaud. Minkowski operations for satellite antenna layout.
12. Lanthier, Maheshwari, Sack. Approximating weighted shortest paths on polyhedral surfaces.
13. Berretty, Goldberg, Overmars, van der Stappen. On fence design and the complexity of push plans for orienting parts.
14. Cazals, Puech. Bucket-like space partitioning data structures with applications to ray tracing
15. Hudson, Manocha, Cohen, Lin, Hoff, Zhang. Accelerated occlusion culling using shadow frusta.
16. Allen, Dutta. Wall thickness control in layered manufacturing.
17. Liotta, Preparata, Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design.
18. Raghotama, Shapiro Necessary conditions for boundary representation variance.
19. Mehlhorn, Mueller, Naeher, Schirra, Seel, Uhrig, Ziegler. A computational basis for higher dimensional computational geometry: Higher dimensional convex hulls and Delaunay triangulations specification and implementation.

Theoretical Track

1. Müller-Hannemann, Karsten Weihe. Minimum Strictly Convex Quadrangulations of Convex Polygons.
2. Erickson. Space-time Tradeoffs for Emptiness Queries.
3. Agarwal, Sharir, Welzl. The Discrete 2-Center Problem.
4. Agarwal, Aronov, Sharir. On Levels in Arrangements of Lines, Segments, Planes, and Triangles.
5. Chan. Approximate Nearest Neighbor Queries Revisited.
6. Tarasov, Vyalyi. Some PL functions on surfaces are not height functions.
7. Aronov, Fortune. Average-Case Ray Shooting and Minimum Weight Triangulations.
8. Károlyi, Pach, Tóth. Ramsey-Type Theorems for Geometric Graphs.
9. de Berg, Katz, van der Stappen, Vleugels. Realistic Input Models for Geometric Algorithms.
10. Efrat, Sharir. On the Complexity of the Union of Fat Objects in the Plane.
11. Har-Peled. Approximate Shortest Paths and Geodesic Diameters on Convex Polytopes in Three Dimensions.
12. Akutsu, Tamaki, Tokuyama. Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Set.
13. Mehlhorn, Shermer, Yap. A Complete roundness Classification Procedure.
14. Bremner, Fukuda, Marzetta. Primal-Dual Methods for Vertex and Facet Enumeration.
15. O'Rourke, Streinu. Vertex-Edge Pseudo-Visibility Graphs: Characterization and Recognition.
16. Ramos. Construction of 1-d lower envelopes and applications.
17. Goodrich, Guibas, Tanenbaum. Snap Rounding Line Segments Efficiently in Two and Three Dimensions .
18. Agarwal, Guibas, Murali, Vitter. Cylindrical Static and Kinetic Binary Space Partitions.
19. Basch, Guibas, Zhang. Proximity Problems on Moving Points.
20. van Kreveld, van Oostruma, Bajaj, Pascucci, Schikore. Contour Trees and Small Seed Sets for Isosurface Traversal.
21. García, Ramos. Fitting a set of points by a circle.

Short Communications

Applied Track

1. Melkemi. A-Shapes and their derivatives.
2. Gallier. Drawing closed rational surfaces.
3. Kim, Guibas, Shin. Fast collision detection among multiple moving spheres.
4. Kobbelt. Robust and efficient evaluation of functionals on parametric surfaces.
5. Shneerson, Tal. GASP-II: A geometric algorithm animation system for an electronic classroom
6. Agarwal, Murali, Vitter. Practical techniques for constructing binary space partitions for orthogonal rectangles.
7. Vermeer. Assembling objects through parts correlation.
8. Basch, Guibas, Silverstein, Zhang. A practical evaluation of kinetic data structures.
9. Chew. Guaranteed quality Delaunay meshing in 3D.
10. Sazaklis, Arkin, Mitchell, Skiena. Geometric decision trees for optical character recognition.
11. Chang, Yap. A wavelet approach to foveating images.
12. Snoeyink, van Kreveld. Good orders for incremental (re)constructions.
13. Peters, Stewart, Fussel, Ferguson. Algorithmic tolerances and semantics in data exchange.
14. Hagedoorn, Veltkamp. A general method for partial point set matching
15. Doellner, Hinrichs, Spiegel. An interactive environment for visualizing and animating algorithms.
16. Barequet, Bridgeman, Duncan, Goodrich, Tamassia. Classical Computational Geometry in GeomNet.

Theoretical Track

1. Aichholzer, Chen, Lee, Mukhopadhyay. Voronoi Diagrams for Direction-Sensitive Distances.
2. Rivière. Dynamic visibility in polygonal scenes with the visibility complex.
3. Musin. Properties of the Delaunay Triangulation.
4. Lee, Shin, Kim, Shin, Chwa. New Competitive Strategies for Searching in Unknown Star-Shaped Polygons.
5. Gärtner, Schönherr. Smallest Enclosing Ellipses - fast and exact.
6. Alt, Welzl, Wolfers. Piecewise Linear Approximation of Bézier-Curves.
7. Fössmeier, Kaufmann. On Exact Solutions for the Rectilinear Steiner Problem.
8. Streinu. Clusters of Stars.
9. Basch, Devarajan, Indyk, Zhang. Probabilistic Analysis for Combinatorial Functions of Moving Points.
10. López-Ortiz, Sven Schuierer. Position-Independent Near Optimal Searching and On-line Recognition in Star Polygons.
11. Yamashita, Umemoto, Suzuki, Kameda. Searching for Mobile Intruders in a Polygonal Region by a Group of Mobile Searchers.
12. Poon, Zhu, Chin. A Polynomial Time Solution for Labeling a Rectilinear Map.
13. Bollobás, Das, Gunopulos, Mannila. Time-Series Similarity Problems and Well-Separated Geometric Sets.
14. Böhringer, Donald, Halperin. The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields.
15. Hershberger, Suri. Efficient Breakout Routing in Printed Circuit Boards.
16. Onishi, Imai. Voronoi Diagram in Statistical Parametric Space by Kullback-Leibler Divergence.
17. Schirra. Computing the Minimal Diameter for Moving Points: An Exact Implementation Using Parametric Search.
18. Basch, Guibas, Ramkumar. Sweeping Lines and Line Segments with a Heap.

Thanks to Raimund Seidel for making this list available.