SoCG Acceptance List

[Marshall Bern]

THEORETICAL TRACK:  (27 papers)

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 
     Aichholzer

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 
     Efrat 

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

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

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
     Ramos

Small distortion and volume preserving embedding 
     Rao

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

Strechability of star-like pseudo-visibility graphs 
     Streinu

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
     Devillers 

Topological Beam Tracing, 
     Fortune 

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

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

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
     Pellegrini

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

Computing Roundness is Easy if the Set is Almost Round
     Ramos

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
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme