SoCG Acceptance List

Marshall Bern bern at
Tue Feb 16 14:22:20 PST 1999


Approximation and exact algorithms for minimum-width annuli and shells
     Agarwal, Aronov, Har-Peled, Sharir

Lower bounds for kinetic planar subdivisions
     Agarwal, Basch, de Berg, Guibas, Hershberger

Motion planning of a ball amid polyhedral obstacles in three dimensions
     Agarwal and Sharir

The path of a triangulation 

The table layout problem
     Anderson and Sobti

Polytopes in arrangements 
     Aronov and Dey

Spanning trees crossing few barriers
     Asano, de Berg, Cheong, Guibas, Snoeyink, Tamaki

Geometric algorithms for trap design 
     Beretty, Goldberg, Overmars, van der Stappen

Generalizing ham sandwich cuts to equitable subdivisions
     Bespamyatnikh, Kirkpatrick, Snoeyink

Line and curve segment intersection with restricted predicates
     Boissonat, Snoeyink

Hierarchical vertical decompositions, ray shooting , and circular arc
queries in simple polygons
     Cheng, Cheong, Everett, van Oostrum

Sliver exudation
     Cheng, Dey, Edelsbrunner, Facello, Teng

Folding flat silhouettes and wrapping polyhedral packages:
new results in computational origami 
     Demaine, Demaine, Mitchell

Curve reconstruction: connecting dots with good reason
     Dey, Mehlhorn, Ramos

Edgewise subdivision of a simplex
     Edelsbrunner, Grayson

The complexity of the union of (alpha, beta)-covered objects 

On minimum stars, minimum Steiner stars, and maximum matchings
     Fekete and Meijer

Curve reconstruction, the TSP, and Menger's theorem on length

Kinetic connectivity of rectangles
     Hershberger, Suri

On bisectors for different distance functions
     Icking, Klein, Ma, Nickel, Weibler

Visibility-based pursuit-evasion in a polygonal room with a door
     Lee, Shin, Chwa

New bounds on crossing number
     Pach, Spencer, Toth

On range reporting, ray shooting, and k-level construction

Small distortion and volume preserving embedding 

Sharp bounds on geometric permutation of pairwise disjoint balls
     Smorodinsky, Mitchell, Sharir

Strechability of star-like pseudo-visibility graphs 

Efficient algorithms for maximum regression depth 
     van Kreveld, Mitchell, Rousseeuw, Sharir, Snoeyink, Speckmann

APPLIED TRACK (17 papers)

Error-Bounded Regular Algebraic Spline Curves 
     Bajaj and Xu
Exact Geometric Computation Made Easy
     Burnikel, Fleischer, Mehlhorn, Schirra 

Determining an Optimal Penetration among
Weighted Regions in Two and Three Dimensions
     Chen, Daescu, Hu, Wu and Xu 

On Deletion in Delaunay Triangulations

Topological Beam Tracing, 

Geometric Pattern Matching: A Performance Study
     Gavrilov, Indyk, Motwani and Venkatasubramanian

Crust and Anti-Crust: A One-Step Boundary and Skeleton Extraction Algorithm

H-Walk: Hierarchical Distance Computation for Moving Convex Bodies,
     Guibas, Hsu and Zhang

Interval Methods for Kinetic Simulations
     Guibas and Karavelas

A Core Library for Robust Numeric and Geometric Computation
     Karamcheti, Pechtchanski and Yap 

MAPC: A library for Efficient and Exact Manipulation
of Algebraic Points and Curves
     Keyser, Culver, Manocha and Krishnan

One-sided Smoothing of Polygons 
     Lutterkort and Peters:

A Geometric Approach to Computing Higher-Order Form Factors

Controlled Perturbation for Arrangements of Polyhedral Surfaces
with Application to Swept Volumes

Computing Roundness is Easy if the Set is Almost Round

Empirical Design of Geometric Algorithms
     Weihe, Brandes, Liebers, Muller-Hannemann, Wagner and Willhalm

Motion Planning for a Rigid Body Using Random Networks
on the Medial Axis of the Free Space
     Wilmarth, Amato and Stiller 

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme

More information about the Compgeom-announce mailing list