Mathematical Sciences Research Institute

Home » Mathematical Foundations of Geometric Algorithms


Mathematical Foundations of Geometric Algorithms October 13, 2003 - October 17, 2003
Registration Deadline: October 17, 2003 over 15 years ago
To apply for Funding you must register by: July 13, 2003 almost 16 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 Ph.D.'s, 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

MSRI does not hire an outside company to make hotel reservations for our workshop participants, or share the names and email addresses of our participants with an outside party. If you are contacted by a business that claims to represent MSRI and offers to book a hotel room for you, it is likely a scam. Please do not accept their services.

MSRI has preferred rates at the Hotel Shattuck Plaza, depending on room availability. Guests can call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Institute discount. To book online visit this page (the MSRI rate will automatically be applied).

MSRI has preferred rates at the Graduate Berkeley, depending on room availability. Reservations may be made by calling 510-845-8981. When making reservations, guests must request the MSRI preferred rate. Enter in the Promo Code MSRI123 (this code is not case sensitive).

MSRI has preferred rates at the Berkeley Lab Guest House, depending on room availability. Reservations may be made by calling 510-495-8000 or directly on their website. Select "Affiliated with the Space Sciences Lab, Lawrence Hall of Science or MSRI." When prompted for your UC Contact/Host, please list Chris Marshall (coord@msri.org).

MSRI has a preferred rates at Easton Hall and Gibbs Hall, depending on room availability. Guests can call the Reservations line at 510-204-0732 and ask for the MSRI- Mathematical Science Research Inst. rate. To book online visit this page, select "Request a Reservation" choose the dates you would like to stay and enter the code MSRI (this code is not case sensitive).

Additional lodging options may be found on our short term housing page.

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
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
02:00 PM - 03:00 PM
  Geometric computing with uncertain, missing, or overabundant data
Bernard Chazelle