SoCG 2000 Program & Registration Information

[Otfried Cheong]

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:

             http://www.cs.ust.hk/tcsc/scg00.html

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


PRELIMINARY PROGRAM
-------------------

Sunday, June 11

    6:00  Reception


Monday, June 12

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

    	9:20
	Triangulations in CGAL
	J. D. Boissonnat, INRIA, O. Devillers, INRIA,  M. Teillaud, INRIA,
	and M. Yvinec, INRIA
	
    	9:40
	Improving the Surface Cycle Structure for Hexahedral Mesh Generation
	Matthias Mueller-Hannemann, Technische U. Berlin
	
    	10:00
	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
    	1:30
	Point sets with many k-sets
	Geza Toth, MIT

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

    	2:30
	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

    	2:50
	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
    	3:40
	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,

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

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

    	4:40
	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.

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

	5:20
	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:
    	9:00
	Fast Software for Box Intersections
	Afra Zomorodian, UI Urbana Champaign and 
	Herbert Edelsbrunner, Duke U. and Raindrop Geomagic

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

    	9:40
	Pitfalls in Computing with Pseudorandom Determinants
	Bernd Gaertner, ETH Zurich

    	10:00
	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
    	1:30
	When Crossings Count - Approximating the Minimum Spanning Tree
	Sariel Har-Peled, Duke U. and Piotr Indyk, Stanford U.
	
    	1:50
	Linear Programming Queries Revisited
	Edgar A. Ramos, MPI

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

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

    	2:50
	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:
    	3:40 
	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

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

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

    	4:40
	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:
    	9:00
	Reachability by paths of bounded curvature in convex polygons
	Hee-kap Ahn, HKUST, Otfried Cheong, HKUST, 
	Jiri Matousek, Charles U., and Antoine Vigneron, HKUST

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

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

    10:20 Break

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

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

    	11:30
	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

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


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

    	3:40
	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
    
    	4:20
	Delaunay Triangulations and Voronoi Diagrams for Riemannian
	Greg Leibon, Dartmouth  and David Letscher, Oklahoma State

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




-------------
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
Now archived at http://uiuc.edu/~sariel/CG/compgeom/maillist.html.