SCG'00: List of Accepted Papers

Pankaj Kumar Agarwal pankaj at
Sun Feb 13 15:06:32 PST 2000


Theory Track

Point sets with many k-sets
Geza Toth

Testing the congruence of $d$-dimensional point sets
Peter Brass and Christian Knauer

Sweep Algorithms for Constructing Higher-Dimensional Constrained Delaunay Triangulations
Jonathan Richard Shewchuk

An Improved bound for $k$-Sets in Three Dimensions
Micha Sharir and Shakhar Smorodinsky and Gabor Tardos

Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus
Timothy M. Chan

Origin-Embracing Distributions  or A Continuous Analogue of the Upper Bound Theorem
Uli Wagner and Emo Welzl

Surface reconstruction simplified
Nina Amenta, Sunghee Choi, Tamal K. Dey and Naveen Leekha

Random Sampling in Geometric Optimization: New Insights and Applications
Bernd Gaertner and Emo Welzl

Cutting glass
Janos Pach and Gabor Tardos

Reachability by paths of bounded curvature in convex polygons
Hee-kap Ahn and Otfried Cheong and Jiri Matousek and Antoine Vigneron

Linear-Time Polygon Triangulation Made Easy Via Randomization
Nancy M. Amato and Michael T. Goodrich and Edgar A. Ramos

Kinetic Connectivity for Unit Disks
Leonidas Guibas and John Hershberger and Subhash Suri and Li Zhang

Exact and Efficient Unions of balls.
Nina Amenta and Ravi Kolluri

When Crossings Count - Approximating the Minimum Spanning Tree
Sariel Har-Peled and Piotr Indyk

Multivariate regression depth
Marshall Bern and David Eppstein

The 2-Center Problem with Obstacles
Dan Halperin and Micha Sharir and Ken Goldberg

I/O-Efficient Dynamic Planar Point Location
Lars Arge and Jan Vahrenhold

Kinetic Collision Detection for Simple Polygons
David Kirkpatrick and Jack Snoeyink and Bettina Speckmann

Point Set Labeling with Specified Positions
Srinivas Doddi and Madhav V. Marathe and Bernard M.E. Moret

A Helly-type theorem for hyperplane transversals to well-separated convex sets
Boris Aronov and Jacob E. Goodman and Richard Pollack and Rephael Wenger

On the continuous Weber and k-means problems
S.P.Fekete and J.S.B.Mitchell and K.Weinbrecht

Deterministic Algorithms for 3-D Diameter and some 2-D Lower Envelopes
Edgar A. Ramos

Delaunay Triangulations and Voronoi Diagrams for Riemannian
Greg Leibon and David Letscher

A Trace Bound for the Hereditary Discrepancy
Bernard Chazelle and Alexey Lvov

Linear Programming Queries Revisited
Edgar A. Ramos

Applied Track

Smooth shape reconstruction
Jean-Daniel Boissonnat and Frederic Cazals

An algorithm for searching a polygonal region with a flashlight
Steven M. Lavalle and Borislav Simov and Giora Slutzki

Fast Software for Box Intersections
Afra Zomorodian and Herbert Edelsbrunner

Computing with Minkowski sums 
Ioannis Z Emiris

Algebraic methods and arithmetic filtering for exact predicates on circle arcs
Olivier Devillers  and  Alexandra Fronville  and  Bernard Mourrain  and  Monique Teillaud

Reconstructing curves with sharp corners
Tamal K. Dey and Rafe Wenger

Densest Translational Lattice Packing of Non-Convex Polygons
Victor J. Milenkovic

Pitfalls in Computing with Pseudorandom Determinants
Bernd Gaertner

LOOK - A Lazy Object-Oriented Kernel for Geometric Computation
Stefan Funke

Computing Approximate Shortest Paths on Convex Polytopes
Pankaj K. Agarwal and Sariel Har-Peled and Meetesh Karia

Voronoi-based interpolation with higher continuity
Hisamoto Hiyoshi and Kokichi Sugihara

Mesh Generation for Domains with Small Angles
Jonathan Richard Shewchuk

Triangulations in CGAL
J. D. Boissonnat and O. Devillers and M. Teillaud and M. Yvinec

An Efficient, Exact, and Generic Quadratic Programming Solver for 
Geometric Optimization
Bernd Gaertner and Sven Schoenherr

Improving the Surface Cycle Structure for Hexahedral Mesh Generation
Matthias Mueller-Hannemann

The Analysis of a Simple k-Means Clustering Algorithm
T. Kanungo and D. M. Mount and N. S. Netanyahu and C. Piatko and 
R. Silverman and A. Y. Wu

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

More information about the Compgeom-announce mailing list