Home /  Mathematical Foundations of Geometric Algorithms


Mathematical Foundations of Geometric Algorithms October 13, 2003 - October 17, 2003
Registration Deadline: October 17, 2003 almost 21 years ago
To apply for Funding you must register by: July 13, 2003 about 21 years ago
Parent Program:
Organizers Pankaj Agarwal, Herbert Edelsbrunner, Micha Sharir, and Emo Welzl

Show List of Speakers

The workshop will focus on the design and analysis of geometric algorithms, and on the mathematical and algorithmic techniques needed to make these algorithms efficient. The emphasis will be on research topics that are currently active, and they will be presented by key researchers who will survey the current state of the art in these areas, and report on new research results. Some of the topics we plan to focus on are: Geometric algorithms in higher dimensions Geometric algorithms for Bioinformatics Computational topology Arrangements of surfaces and their applications Combinatorial optimization in the geometric setting Robustness in geometric computing Approximation algorithms in geometric optimization Embedding of metric spaces and their algorithmic applications Sublinear algorithms Kinetic data structures Geometric algorithms for mathematical finance Mesh generation Making geometric algorithms efficient via perturbation Algorithms for real algebraic geometry By bringing together leading researchers working on these and related areas, we expect fruitful interaction that will involve them, as well as students, postdocs, and other participants. Consequently, ample free time will be allocated for discussions and collaboration. The invited speakers include: Pankaj Agarwal (Duke) Nina Amenta (Davis) Timothy Chan (Waterloo) Bernard Chazelle (Princeton) Otfried Cheong (Eindhoven) Kenneth Clarkson (Bell Laboratories) Herbert Edelsbrunner (Duke) Bernd Gaertner (ETH Zurich) Leo Guibas (Stanford) Dan Halperin (Tel Aviv) Sariel Har-Peled (Urbana-Champaign) Patrice Koehl (Stanford) Vladlen Koltun (Berkeley) Joe Mitchell (Stony Brook) David Mount (Maryland) Marie-Francoise Roy (Rennes) Jonathan Shewchuk (Berkeley) Shakhar Smorodinsky (Berkeley) Jack Snoeyink (North Carolina) Subhash Suri (Santa Barbara) Kasturi Varadarajan (Iowa) Santosh Vempala (MIT) Uli Wagner (Berkeley)
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Funding & Logistics Show All Collapse

Show Funding

To apply for funding, you must register by the funding application deadline displayed above.

Students, recent PhDs, women, and members of underrepresented minorities are particularly encouraged to apply. Funding awards are typically made 6 weeks before the workshop begins. Requests received after the funding deadline are considered only if additional funds become available.

Show Lodging

For information about recommended hotels for visits of under 30 days, visit Short-Term Housing. Questions? Contact coord@slmath.org.

Show Directions to Venue

Show Visa/Immigration

Schedule, Notes/Handouts & Videos
Show Schedule, Notes/Handouts & Videos
Show All Collapse
Oct 13, 2003
09:15 AM - 10:15 AM
  Approximate Voronoi diagrams
David Mount
10:30 AM - 11:00 AM
  Complexity and computation of 3D Delaunay triangulations
Annamaria Amenta (University of California, Davis)
11:00 AM - 11:30 AM
  Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation Anisotropic Voronoi diagrams and guaranteed-quality Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation
Jonathan Shewchuk
11:30 AM - 12:00 PM
  Pragmatic point ordering for Delaunay tessellation Pragmatic point ordering for Delaunay tessellation in 3D and 4D
Jack Snoeyink
02:00 PM - 02:45 PM
  On conflict-free colorings
Meir Smorodinsky
04:15 PM - 05:15 PM
  PL implementations of differential topology concepts and their applications
Herbert Edelsbrunner (Duke University)
Oct 14, 2003
09:00 AM - 10:00 AM
  Geometric approximation using core sets
Pankaj Agarwal (Duke University)
10:30 AM - 11:00 AM
  On core sets and shape fitting in high dimensions
Sariel Har-Peled
11:00 AM - 11:30 AM
  On some geometric optimal path and network problems problems
Joseph Mitchell
11:30 AM - 12:00 PM
  What is new with kinetic data structures?
Leo Guibas
02:00 PM - 03:00 PM
  Problems on the interface of geometry and economics
Subhash Suri
03:30 PM - 04:30 PM
  Arrangements of surfaces: A state of the art report
Vladlen Koltun
Oct 15, 2003
09:00 AM - 10:00 AM
  Linear algebra and LP-type problems
Bernd Gaertner
10:30 AM - 11:00 AM
  Bernstein basis and real rool isolation
Marie-Francoise Roy
11:00 AM - 11:30 AM
  Computational complexity of stabbing, visibility and radii computations
Thorsten Theobald
11:30 AM - 12:00 PM
  Efficient algorithms for bichromatic separability
Boris Aronov (New York University)
Oct 16, 2003
09:00 AM - 10:00 AM
  How to compute the volume?
Santosh Vempala (Georgia Institute of Technology)
10:30 AM - 11:00 AM
  Output-sensitive construction of the union of triangles
Eti Ezra
11:00 AM - 11:30 AM
  Monotone paths in line arrangements with a small number of directions
Adrian Dumitrescu
02:00 PM - 02:30 PM
  Bipartite perfect matching in the plane
Kasturi Varadarajan
02:30 PM - 03:00 PM
  Capturing topological and geometric features of molecular surfaces for protein docking
Yusu Wang (Univ. California, San Diego)
03:30 PM - 04:30 PM
  Protein shape descriptors
Patrice Koehl
Oct 17, 2003
09:00 AM - 10:00 AM
  Approximation algorithms for diameter, width, and related problems
Timothy Chan
10:30 AM - 11:00 AM
  Binary space partitions
Csaba Toth
11:00 AM - 11:30 AM
  Learning about manifolds from samples
Ulrich Wagner
11:30 AM - 12:00 PM
  Progressive simplification of tetrahedral meshes preserving all isosurface topologies
Yi-Jen Chiang (New York University)
02:00 PM - 03:00 PM
  Geometric computing with uncertain, missing, or overabundant data
Bernard Chazelle