22nd European Workshop on Computational Geometry
March 27-29 2006, Delphi, Greece

The following documents are available in electronic form:

22nd European Workshop on Computational Geometry 2006
European Cultural Center of Delphi

Workshop Program

Sunday, March 26
19:00 Registration & Reception (Lobby of the Guesthouse Europe)       
20:30 End of Sunday registration       

Monday, March 27
9:20 Openning Remarks
9:30 Where to build a temple, and where to dig to find one - G. Aloupis, J. Cardinal, S. Collette, J. Iacono, S. Langerman
9:45 Fixed Parameter Algorithms for Minimum Weight Partitions - C. Borgelt, M. Grantson, C. Levcopoulos
10:00 Pseudo-Convex Decomposition of Simple Polygons - S. Gerdjikov, A. Wolff
10:15 The Existence of a Pseudo-triangulation in a given Geometric Graph - A. Schulz
10:30 break
10:40 Ray Shooting Amidst Fat Convex Polyhedra in 3-Space - B. Aronov, M. de Berg, C. Gray
10:55 Approximation of an open polygonal curve with a minimum number of circular arcs - R.L. S. Drysdale, G. Rote, A. Sturm
11:10 How to Sample and Reconstruct Curves With Unusual Features - T. Lenz
11:25 On the Curve Equipartition Problem: a brief exposition of basic issues - C. Panagiotakis, G. Georgakopoulos, G. Tziritas
11:40 coffee break
12:00 Invited talk: Raimund Seidel (U. des Saarlandes, Germany): "Understanding the inverse Ackerman function" (abstract)
13:00 Lunch
15:00 On the density of iterated line segment intersections - A. Gruene, S. Kamali
15:15 On the structure of sets attaining the rectilinear crossing number - O. Aichholzer, D. Orden, P.A. Ramos
15:30 On the all-farthest-segments problem for a planar set of points - A. Mukhopadhyay, S. Chatterjee, B. Lafreniere
15:45 Planar Point Sets with Large Minimum Convex Partitions - J. Garcia-Lopez, C. Nicolas
16:00 break
16:10 Kinetic Collision Detection for BallsRolling on a Plane - M.A. Abam, M.de Berg, S-H. Poon, B. Speckmann
16:25 Computing Shortest Paths amidst Growing Discs in the Plane - J. van den Berg, M. Overmars
16:40 Few Optimal Foldings of HP Protein Chains on Various Lattices - S.-H. Poon, S. Thite
16:55 Reconfiguring planar dihedral chains - G. Aloupis, H. Meijer
17:10 coffee break
17:30 Gray Code Enumeration of Plane Straight-Line Graphs - O. Aichholzer, F. Aurenhammer, C. Huemer, B. Vogtenhuber
17:45 The Rotation Graph of k-ary trees is Hamiltonian - C. Huemer, F. Hurtado, J. Pfeifle
18:00 Cover Contact Graphs - M. Abellanas, N. Atienza, N. de Castro, C. Cortes, M.A. Garrido, C.I. Grima, G. Hernandez, A. Marquez, A. Moreno,
J.R. Portillo, P. Reyes, J. Valenzuela, M.T. Villar
18:15 A binary labelling for plane Laman graphs and quadrangulations - C. Huemer, S. Kappes
18:45 Business Meeting

Tuesday, March 28
9:00 Helly-Type Theorems for Line Transversals to Disjoint Unit Balls - O. Cheong, X. Goaoc, A. Holmsen, S. Petitjean
9:15 Geometric realization of a projective triangulation with one face removed - C. Bonnington, A. Nakamoto, K. Ohba
9:30 Splitting (Complicated) Surfaces Is Hard - E. Chambers, E. Colin de Verdiere, J. Erickson, F. Lazarus, K. Whittlesey
9:45 Pants Decomposition of the Punctured Plane - S.-H. Poon, S. Thite
10:00 break
10:10 Computing the Frechet Distance Between Simple Polygons - K. Buchin, M. Buchin, C. Wenk
10:25 Probabilistic matching of sets of polygonal curves - H. Alt, L. Scharf, S. Scholz
10:40 On the ICP Algorithm - E. Ezra, M. Sharir, A. Efrat
10:55 Noisy disk set matching under rigid motion - Y. Diez, J.A. Sellares
11:10 coffee break
11:30 Invited talk: Bernard Chazelle (Princeton U., USA): "So Much Data, So Little Time" (abstract)
12:30 Lunch
14:30 Visit of archaeological site and museum
16:00 Restricted Mesh Simplification using Edge Contractions - M. Andersson, J. Gudmundsson, C. Levcopoulos
16:15 Guaranteed-Quality Anisotropic Mesh Generation for Domains with Curvers - GY. Yokosuka, K. Imai
16:30 Modifying Delaunay Refined Two-Dimensional Triangular Meshes - N. Coll, M. Guerrieri, J.A. Sellares
16:45 Mesh optimisation based on Willmore energy - L. Alboul, W. Brink, M. Rodrigues
17:00 break
17:10 A new Approximation Algorithm for Labeling Weighted Points with Sliding Labels - T. Erlebach, T. Hagerup, K. Jansen, M. Minzlaff, A. Wolff
17:25 A polynomial-time approximation algorithm for a geometric dispersion problem - M. Benkert, J. Gudmundsson, C. Knauer,E. Moet, R. van Oostrum, A. Wolff
17:40 Covering a Set of Points with a Minimum Number of Lines - M. Grantson, C. Levcopoulos
17:55 Min-max-min Geometric Facility Location Problems - J. Cardinal, S. Langerman
18:10 coffee break
18:30 Proximity structures in the fixed orientation metrics - C. Wulff-Nilsen
18:45 Randolphs Robot Game is NP-complete! - B. Engels, T. Kamphans
19:00 Visibility Map determination using angle preprocessing - L. Ortega, A.J. Rueda, F. Feito
19:15 Maximizing the Guarded Interior of an Art Gallery - I. Emiris, C. Fragoudakis, E. Markou
20:30 Workshop Dinner

Wednesday, March 29
9:00 On Realistic Terrains - E. Moet, M. van Kreveld, A. F. van der Stappen
9:15 River networks and watershed maps of triangulated terrains revisited - H.-K. Ahn, M. de Berg, O. Cheong, H. Haverkort, F. van der Stappen, L. Toma
9:30 In-Place Randomized Slope Selection - H. Blunck, J. Vahrenhold
9:45 In-Place Algorithms for Computing (Layers of) Maxima - H. Blunck, J. Vahrenhold
10:00 break
10:10 Finding enclosing boxes with empty intersection - C. Cortes, J.M. Diaz-Banez, J. Urrutia
10:25 Inner approximation of polygons and polyhedra by unions of boxes - C. Spielberger, M. Held
10:40 On the Bounding Boxes Obtained by Principal Component Analysis - D. Dimitrov, C. Knauer, K. Kriegel, G. Rote
10:55 Algorithms for Maximizing the Volume of Intersection of Polytopes - K. Fukuda, T. Uno
11:10 coffee break
11:30 Invited talk: Monique Teillaud (INRIA Sophia-Antipolis, France): "From Triangles to Curves" (abstract)
12:30 Lunch
14:30 On Embedding a Graph on Two Sets of Points - E Di Giacomo, G. Liotta, F. Trotta
14:45 Acyclic Orientation of Drawings - E. Ackerman, K. Buchin, C. Knauer, G.Rote
15:00 A homotopy theorem for arrangements of double pseudolines - L. Habert, M. Pocchiola
15:15 Tight planar packings of two trees - Y. Oda, K. Ota
15:30 break
15:40 A Topologically Robust Boolean Algorithm Using Approximate Arithmetic - J. Smith, N.A. Dodgson
15:55 A small improvement in the walking algorithm for point location in a triangulation - I. Kolingerova
16:10 A certified algorithm for the InCircle predicate among ellipses - I.Z. Emiris, E.P. Tsigaridas, G.M. Tzoumas
16:25 Voronoi diagrams in CGAL - M.I. Karavelas
16:40 Conclunding Remarks

B. Chazelle will also give a talk at DIKEMES in Athens on Thursday, March 30, 2006 at 19:30, as an invitee of the Princeton Club of Greece.

Last modified: 3 May 2006