Sponsor: Deutsche Forschungsgemeinschaft (DFG)

Workshop Program


Room M2
Lecture Hall Building
Department of Mathematics and Computer Science
Einsteinstr. 64
D-48149 Münster

Thursday, March 28, 1996

7:45  Registration

8:20  Welcome and Introduction

Session 1: 8:30-9:50
Chair:  F. Aurenhammer (TU Graz)

8:30  Results on fat objects with a low intersection proportion
	  M. Wolfrath (U Würzburg)
8:50  Range searching in low-density environments
	  O. Schwarzkopf (Postech, South Korea), J. Vleugels (Utrecht U)
9:10  Computing the convex hull of a simple polygon on the sphere
	  F. Weller, C. Kirstein (U Dortmund)
9:30  Three-dimensional restricted-orientation convexity
	  E. Fink (Carnegie Mellon U), D. Wood (U Hongkong)

9:50-10:20  Coffee Break

Session 2: 10:20-12:35
Chair:  G. Toussaint (McGill U)

10:20  New greedy triangulation algorithms
	   O. Aichholzer, F. Aurenhammer, G. Rote (TU Graz),
	   Y.-F. Xu (U Xi'an Jiaotong)
10:40  The edge-flipping distance of triangulations
	   S. Hanke, T. Ottmann, S. Schuierer (U Freiburg)
11:00  Flipping edges in triangulations of polygons and point sets
	   F. Hurtado, M. Noy (U Politecnica de Catalunya),
	   J. Urrutia (U Ottawa)
11:20  The polytope of all triangulations of a point configuration
	   J. A. de Loera (U Minnesota), S. Hosten (Cornell U),
	   F. Santos (U Cantabria Santander),
	   B. Sturmfels (U California Berkeley)
11:40  Short Break

11:45  Invited Talk:
       Smooth surfaces for multi-scale shape representation
           H. Edelsbrunner (U of Illinois at Urbana-Champaign)

12:35-14:00  Lunch Break

Session 3: 14:00-15:20
Chair:  P. Gritzmann (U Trier)

14:00  Incidence angle constrained visibility
	   G. Blanco, J. G. Lopez (U Pol. Madrid),
           F. Hurtado (U Pol. Catalunya), P. Ramos (U Politecnica Madrid),
           V. Sacristan (U Pol. Catalunya)
14:20  The illumination problem of L. Fejes Toth revisited
	   M. Pocchiola (ENS Paris Cedex), G. Vegter (U Groningen)
14:40  Rectangle and box visibility graphs in 3D
           S. Fekete (U Köln), H. Meijer (Utrecht U and Queens U, 
15:00  Dealing with degeneracies and numerical imprecisions when
       computing visibility graphs
	   S. Riviere (iMAGIS-IMAG Grenoble)

15:20-15:50  Coffee Break

Session 4: 15:50-17:50
Chair:  H. Alt (FU Berlin)

15:50  Experimental comparison of quadrangulation algorithms
       for sets of points
	   P. Bose (U of British Columbia),
	   S. Ramaswami, G. Toussaint, A. Turki (McGill U)
16:10  Calculating Voronoi diagrams using convex sweep curves
	   U. Kühn (U Münster)
16:30  Computing periodic Voronoi partitions on the Euclidean plane
	   M. Mazon, D. Bochis (U Cantabria Santander)
16:50  Short Break

17:00  Invited Talk: 
       Fixture design
	   M. Overmars (Utrecht U)
18:00  Business Meeting: GI Fachgruppe Algorithmische Geometrie

19:30  Workshop dinner at "Pinkus Müller"

Friday, March 29, 1996

Session 5: 8:30-9:50
Chair:  M. Pocchiola (ENS Paris Cedex)

8:30  Representation of geometric objects as set of inequalities
	  A. Frank, P. Haunold, W. Kuhn, G. Kuipers (TU Wien)
8:50  Exact volume computation for polytopes: A practical study
	  B. Büler, A. Enge, K. Fukuda, H.-J. Luethi (ETH Zürich)
9:10  Answering Line Segment Intersection Queries Based On Sample Answers
	  A. Hinkenjann, M. Kukuk, H. Müller (U Dortmund)
9:30  Discrete simplicial complexes
	  W. Hölbling, W. Kuhn, A. U. Frank (TU Wien)

9:50-10:20  Coffee Break

Session 6: 10:20-12:35
Chair:  R. Klein (FernU Hagen)

10:20  Determination of finite sets by X-rays
          R. J. Gardner (Western Washington U, Bellingham),
          P. Gritzmann (U Trier)
10:40  Reference points for shape matching
          H. Alt, U. Fuchs (FU Berlin),
          G. Rote (TU Graz), G. Weber (FU Berlin)
11:00  Measuring circularity of a set of points
          J. Garcia, P. A. Ramos (U Politecnica Madrid)
11:20  Orientation independent covering of point sets in R^2
       with pairs of rectangles or optimal squares
          J. W. Jaromczyk (U Kentucky, Lexington), M. Kowaluk (Warsaw U)

11:40  Short Break

11:45  Invited Talk: 
       Improved p-Center algorithms
          M. Sharir (Tel-Aviv U and Courant Institute, NYU)

12:35-14:00  Lunch Break

Session 7: 14:00-15:40
Chair:  G. Vegter (U Groningen)

14:00  Hierarchical Motion planning using a spatial index
           K. Verbarg, A. Hensel (U Würzburg)
14:20  Optimal robot localization in trees
           K. Romanik (Rutgers U), S. Schuierer (U Freiburg)
14:40  Subquadratic algorithms for the general collision detection problem
           E. Schoemer (U des Saarlandes),
           C. Thiel (MPII Saarbrücken)
15:00  Dynamic collision detection algorithms in computational geometry
           M. Gavrilova, J. Rokne, D. Gavrilov  (U Calgary)
15:20  An efficient competitive strategy for learning a polygon
           F. Hoffmann (FU Berlin), C. Icking, R. Klein (FernU Hagen),
           K. Kriegel (FU Berlin)

15:40-16:10  Coffee Break

Session 8: 16:10-17:50
Chair: F. Hurtado (U Pol. Catalunya)

16:10  Optimization problems related to Zigzag pocket machining
           E. Arkin (SUNY Stony Brook), M. Held (U Salzburg),
           C. Smith (SUNY Stony Brook)
16:30  Computing the Minkowski sum of monotone polygons
           A. H. Barrera (U Hiroshima)
16:50  Morphing fields of directions defined on triangulations
       to morph simple polygons
           A. Oliveira, S. do Nascimento, S. Meerbaum 
           (Federeal U Rio de Janeiro)
17:10  Fast Stabbing of boxes in high dimensions
           F. Nielsen (U of Nice Sophia-Antipolis)
17:30  Sequential and parallel construction of (1/r)-approximations
           P. Knieper, A. Srivastav (Humboldt U Berlin)

17:50  End of workshop