SoCG 2000 Program & Registration Information

Otfried Cheong otfried at
Mon Apr 17 19:17:59 PDT 2000

The conference website for the 16th ACM Symposium on Computational
Geometry in Hong Kong is open, with the preliminary program (an ASCII
version is attached below), general information about the conference
and the conference site, and the registration form.

The early registration deadline is May 14.  We would encourage you not
to wait that long, since our supply of hotel-quality housing on campus
is limited, and accomodation is reserved on a first-come-first-serve
basis.  (To be to the point, there are not enough hotel-quality rooms
for all participants.  Once they are gone you'll have to stay in a
dormitory room or off-campus.)

You can find the conference website at the following URL:


The organizing team
Siu-Wing Cheng, Otfried Cheong
Hong Kong University of Science and Technology


Sunday, June 11

    6:00  Reception

Monday, June 12

    Session 1, Applied Track
    Session Chair:
	Mesh Generation for Domains with Small Angles
	Jonathan Richard Shewchuk, UC Berkeley

	Triangulations in CGAL
	J. D. Boissonnat, INRIA, O. Devillers, INRIA,  M. Teillaud, INRIA,
	and M. Yvinec, INRIA
	Improving the Surface Cycle Structure for Hexahedral Mesh Generation
	Matthias Mueller-Hannemann, Technische U. Berlin
	Computing with Minkowski sums
	Ioannis Z Emiris, INRIA

    10:20  Break 

    10:50  Invited Talk
	   Fred Richards, Yale U.

    11:50  Lunch

    Session 2, Theory Track
    Session Chair: Pankaj Agarwal
	Point sets with many k-sets
	Geza Toth, MIT

	An Improved bound for $k$-Sets in Three Dimensions
	Micha Sharir, Tel Aviv U., Shakhar Smorodinsky, Tel Aviv U.,  
	and Gabor Tardos, Hungarian Academy
	Origin-Embracing Distributions or A Continuous Analogue of
	the Upper Bound Theorem
	Uli Wagner, ETH Zurich and Emo Welzl, ETH Zurich

	A Helly-type theorem for hyperplane transversals to well-separated 
	convex sets
	Boris Aronov, Poly U.,  Jacob E. Goodman, CUNY,
	Richard Pollack, Courant Inst., and Rephael Wenger, Ohio State

	A Trace Bound for the Hereditary Discrepancy
	Bernard Chazelle, Princeton and Alexey Lvov, Princeton
    	3:10   Break

    Session 3, Theory/Applied Track

    Session Chair: Herbert Edelsbrunner
	On the continuous Weber and k-means problems
	S.P. Fekete, Tech. U.,  J.S.B. Mitchell, SUNY Stony Brook,  
	and K. Weinbrecht, U. K\"oln,

	The 2-Center Problem with Obstacles
	Dan Halperin, Tel Aviv U., Micha Sharir, Tel Aviv U.,
	and Ken Goldberg, UC Berkeley

	Random Sampling in Geometric Optimization: New Insights and
	Bernd Gaertner, ETH Zurich and Emo Welzl, ETH Zurich

	The Analysis of a Simple k-Means Clustering Algorithm
	T. Kanungo, U. Maryland, D. M. Mount, U. Maryland, 
	N. S. Netanyahu, U. Maryland, C. Piatko, Johns Hopkins, 
	R. Silverman, U. of the District of Columbia, and A. Y. Wu,
	American U.

	An Efficient, Exact, and Generic Quadratic Programming Solver for
	Geometric Optimization
	Bernd Gaertner, ETH Zurich and Sven Schoenherr, Freie U.

	Exact and Efficient Unions of balls.
	Nina Amenta, UT Austin and Ravi Kolluri, UT Austin

    8:00    Business meeting


Tuesday, June 13

    Session 4, Applied Track
    Session Chair:
	Fast Software for Box Intersections
	Afra Zomorodian, UI Urbana Champaign and 
	Herbert Edelsbrunner, Duke U. and Raindrop Geomagic

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

	Pitfalls in Computing with Pseudorandom Determinants
	Bernd Gaertner, ETH Zurich

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

    10:20  Break

    10:50  Invited Talk
	   Andrew Frank, Technical U.

    11:50  Lunch

    Session 5, Theory Track
    Session Chair: Mark de Berg
	When Crossings Count - Approximating the Minimum Spanning Tree
	Sariel Har-Peled, Duke U. and Piotr Indyk, Stanford U.
	Linear Programming Queries Revisited
	Edgar A. Ramos, MPI

	Point Set Labeling with Specified Positions
	Srinivas Doddi, U. New Mexico, Madhav V. Marathe, Los
	Alamos, and Bernard M.E. Moret, U. New Mexico

	I/O-Efficient Dynamic Planar Point Location
	Lars Arge, Duke U. and Jan Vahrenhold U. M\"unster

	Linear-Time Polygon Triangulation Made Easier Via Randomization
	Nancy M. Amato, Texas A&M, Michael T. Goodrich, JHU,
	and Edgar A. Ramos, MPI

    3:10   Break

    Session 6, Applied/Theory  Track
    Session Chair:
	A simple algorithm for homeomorphic surface reconstruction
	Nina Amenta, UT Austin, Sunghee Choi, UT Austin,
	Tamal K. Dey, Ohio State,  and Naveen Leekha, Ohio State

	Smooth shape reconstruction
	Jean-Daniel Boissonnat, INRIA, and Frederic Cazals, INRIA

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

	Voronoi-based interpolation with higher continuity
	Hisamoto Hiyoshi, U. Tokyo,  and Kokichi Sugihara, U. Tokyo

    7:00 Conference Banquet


Wednesday, June 14

    Session 7, Applied/Theory Track
    Session Chair:
	Reachability by paths of bounded curvature in convex polygons
	Hee-kap Ahn, HKUST, Otfried Cheong, HKUST, 
	Jiri Matousek, Charles U., and Antoine Vigneron, HKUST

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

	Computing Approximate Shortest Paths on Convex Polytopes
	Pankaj K. Agarwal, Duke U., Sariel Har-Peled, Duke U.,
	and Meetesh Karia, Trilogy
	Densest Translational Lattice Packing of Non-Convex Polygons
	Victor J. Milenkovic, U. Miami

    10:20 Break

    Session 8, Theory Track
    Session Chair: Franz Aurenhammer
	Deterministic Algorithms for 3-D Diameter and some 2-D Lower Envelopes
	Edgar A. Ramos, MPI

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

	Testing the congruence of $d$-dimensional point sets
	Peter Brass, Freie U. and Christian Knauer, Freie U.

    11:50  Lunch

    1:30  Invited Talk

	  Jean-Clause Latombe, Stanford U.

    2:30   Break

    Session 9, Theory Track
    Session Chair: Hazel Everett

	Multivariate regression depth
	Marshall Bern, Xerox and David Eppstein, UC Irvine

	Kinetic Collision Detection for Simple Polygons
	David Kirkpatrick, UBC, Jack Snoeyink, UNC Chapel Hill, 
	and Bettina Speckmann, UBC

	Kinetic Connectivity for Unit Disks
	Leonidas Guibas, Stanford U., John Hershberger, Mentor
	Graphics, Subhash Suri, Washington U., and Li Zhang, Stanford U.

    4:00 Break

    Session 10, Theory Track
    Session Chair: Jeff Erickson
	Delaunay Triangulations and Voronoi Diagrams for Riemannian
	Greg Leibon, Dartmouth  and David Letscher, Oklahoma State

	Sweep Algorithms for Constructing Higher-Dimensional
        Constrained Delaunay Triangulations
        Jonathan R. Shewchuk, UC

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