computational geometry

Categorized List of All Problems

Below, each category lists the problems that are classified under that category. Note that each problem may be classified under several categories.

arrangements:

• 3-Colorability of Arrangements of Great Circles (Problem 44)

art galleries:

• Vertex -Floodlights (Problem 23)

coloring:

• 3-Colorability of Arrangements of Great Circles (Problem 44)

combinatorial geometry:

• k-sets (Problem 7)
• Binary Space Partition Size (Problem 14)
• Chromatic Number of the Plane (Problem 57)
• Counting Polyominoes (Problem 37)
• Distances among Point Sets in ² and ³ (Problem 39)
• Extending Pseudosegment Arrangements by Subdivision (Problem 34)
• Lines Tangent to Four Unit Balls (Problem 61)
• Monochromatic Triangles (Problem 58)
• Pushing Disks Together (Problem 18)
• Rolling a Die over a Labeled Board (Problem 68)
• Slicing Axes-Parallel Rectangles (Problem 74)
• The Number of Pointed Pseudotriangulations (Problem 40)
• Thrackles (Problem 30)
• Union of Fat Objects in 3D (Problem 4)
• Vertical Decompositions in ^d (Problem 19)

convex hulls:

• Dynamic Planar Convex Hull (Problem 12)
• Dynamic Planar Nearest Neighbors (Problem 63)
• Inplace Convex Hull of a Simple Polygonal Chain (Problem 36)
• Output-sensitive Convex Hull in ^d (Problem 15)

data structures:

• Binary Space Partition Size (Problem 14)
• Dynamic Planar Convex Hull (Problem 12)
• Dynamic Planar Nearest Neighbors (Problem 63)
• Point Location in 3D Subdivision (Problem 13)

Delaunay triangulations:

• Flip Graph Connectivity in 3D (Problem 28)
• Stretch-Factor for Points in Convex Position (Problem 71)
• Voronoi Diagram of Moving Points (Problem 2)

dissections:

• Congruent Partitions of Polygons (Problem 73)

folding and unfolding:

• Edge-Unfolding Convex Polyhedra (Problem 9)
• Edge-Unfolding Polycubes (Problem 64)
• General Unfoldings of Nonconvex Polyhedra (Problem 43)
• Vertex-Unfolding Polyhedra (Problem 42)
• Volume Maximizing Convex Shape (Problem 62)

geometric graphs:

• Edge-Coloring Geometric Graphs (Problem 75)
• Thrackles (Problem 30)
• Yao-Yao Graph a Spanner? (Problem 70)

graph drawing:

• 3D Minimum-Bend Orthogonal Graph Drawings (Problem 46)
• Isoceles Planar Graph Drawing (Problem 69)
• Linear-Volume 3D Grid Drawings of Planar Graphs (Problem 51)
• Queue-Number of Planar Graphs (Problem 52)
• Smallest Universal Set of Points for Planar Graphs (Problem 45)
• Thrackles (Problem 30)

graphs:

• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)
• Smallest Universal Set of Points for Planar Graphs (Problem 45)
• Thrackles (Problem 30)
• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

linear programming:

• Linear Programming: Strongly Polynomial? (Problem 8)

lower bounds:

• 3SUM Hard Problems (Problem 11)
• Sorting X + Y (Pairwise Sums) (Problem 41)

meshing:

• Hexahedral Meshing (Problem 27)
• Most Circular Partition of a Square (Problem 59)

minimum spanning tree:

• Bounded-Degree Minimum Euclidean Spanning Tree (Problem 48)
• Euclidean Minimum Spanning Tree (Problem 5)

numerical computations:

• Sum of Square Roots (Problem 33)

optimization:

• Bounded-Degree Minimum Euclidean Spanning Tree (Problem 48)
• Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots (Problem 35)
• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)
• Packing Unit Squares in a Simple Polygon (Problem 56)
• Pallet Loading (Problem 55)
• Planar Euclidean Maximum TSP (Problem 49)
• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

packing:

• Most Circular Partition of a Square (Problem 59)
• Packing Unit Squares in a Simple Polygon (Problem 56)
• Pallet Loading (Problem 55)

partitioning:

• Congruent Partitions of Polygons (Problem 73)
• Fair Partitioning of Convex Polygons (Problem 67)

planar graphs:

• Bar-Magnet Polyhedra (Problem 32)
• Isoceles Planar Graph Drawing (Problem 69)
• Pointed Spanning Trees in Triangulations (Problem 50)

point sets:

• k-sets (Problem 7)
• Bounded-Degree Minimum Euclidean Spanning Tree (Problem 48)
• Magic Configurations (Problem 65)
• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)
• Planar Euclidean Maximum TSP (Problem 49)
• Simple Polygonalizations (Problem 16)
• Smallest Universal Set of Points for Planar Graphs (Problem 45)
• Surface Reconstruction (Problem 26)
• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

point sets.:

• Reflexivity of Point Sets (Problem 66)

polygons:

• Congruent Partitions of Polygons (Problem 73)
• Fair Partitioning of Convex Polygons (Problem 67)
• Hinged Dissections (Problem 47)
• Reflexivity of Point Sets (Problem 66)
• Simple Polygonalizations (Problem 16)
• Transforming Polygons via Vertex-Centroid Moves (Problem 60)

polyhedra:

• 3-Colorability of Arrangements of Great Circles (Problem 44)
• Bar-Magnet Polyhedra (Problem 32)
• Edge-Unfolding Convex Polyhedra (Problem 9)
• Edge-Unfolding Polycubes (Problem 64)
• Equiprojective Polyhedra (Problem 76)
• General Unfoldings of Nonconvex Polyhedra (Problem 43)
• Hamiltonian Tetrahedralizations (Problem 29)
• Polyhedron with Regular Pentagon Faces (Problem 72)
• Vertex-Unfolding Polyhedra (Problem 42)

reconstruction:

• Surface Reconstruction (Problem 26)

robotics:

• Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots (Problem 35)

scheduling:

• Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots (Problem 35)

shortest paths:

• Euclidean Minimum Spanning Tree (Problem 5)
• Minimum Euclidean Matching in 2D (Problem 6)
• Minimum-Link Path in 2D (Problem 22)
• Shortest Paths among Obstacles in 2D (Problem 21)

simplification:

• Polygonal Curve Simplification (Problem 24)
• Polyhedral Surface Approximation (Problem 25)

spanners:

• Stretch-Factor for Points in Convex Position (Problem 71)
• Yao-Yao Graph a Spanner? (Problem 70)

stabbing:

• Minimum Stabbing Spanning Tree (Problem 20)

traveling salesman:

• Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)
• Planar Euclidean Maximum TSP (Problem 49)
• Traveling Salesman Problem in Solid Grid Graphs (Problem 54)

triangulations:

• Compatible Triangulations (Problem 38)
• Flip Graph Connectivity in 3D (Problem 28)
• Hamiltonian Tetrahedralizations (Problem 29)
• Minimum Weight Triangulation (Problem 1)
• Pointed Spanning Trees in Triangulations (Problem 50)
• Simple Linear-Time Polygon Triangulation (Problem 10)
• The Number of Pointed Pseudotriangulations (Problem 40)

visibility:

• Trapping Light Rays with Segment Mirrors (Problem 31)
• Vertex -Floodlights (Problem 23)
• Visibility Graph Recognition (Problem 17)

Voronoi diagrams:

• Dynamic Planar Nearest Neighbors (Problem 63)
• Voronoi Diagram of Lines in 3D (Problem 3)
• Voronoi Diagram of Moving Points (Problem 2)

The European Workshop on Computational Geometry

Upcoming workshops

• 28th EuroCG, 2012, Assisi, Italy, March 19-21, 2012.
• 27th EuroCG, 2011, Morschach, Switzerland, March 28-30, 2011

Past workshops

• 26th EuroCG, 2010, Dortmund, Germany, March 22-24, 2010
• 25th EuroCG, 2009, Brussels, Belgium, March 16-18, 2009
• 24th EuroCG, 2008, Nancy, France, March 18-20, 2008
  Special issue in CGTA, Volume 43, Issue 2, Pages 67-232 (February 2010).
• 23rd EuroCG, 2007, Graz, Austria, March 19-21, 2007 (archive: program, abstracts[.pdf])
  Special issue in CGTA, Volume 42, Issue 8, Pages 723-814 (October 2009).
• 22nd EuroCG, 2006, Delphi, Greece, March 27-29, 2006 (archive: program+abstracts)
  Special issue in CGTA, Volume 41, Issue 1-2, Pages 1-110 (October 2008).
• 21st EuroCG, 2005, Eindhoven, The Netherlands, March 9-11, 2005 (archive: program+abstracts)
  Special issue in CGTA, Volume 36, Issue 1 (January 2007).
• 20th EuroCG, 2004, Seville, Spain, March 24-26, 2004 (archive: program+abstracts)
  Special issue in CGTA, Volume 37, Issue 3 (August 2007).
• 19th EuroCG, 2003, Bonn, Germany, March 24-26, 2003 (archive: CFP, program).
  Special issue in CGTA, Volume 30, Issue 2 (February 2005).
• 18th EuroCG, 2002, Warsaw, Poland, April 10-12, 2002 (archive: CFP, program).
  Special issue in CGTA, Volume 27, Issue 1 (January 2004).
• 17th EuroCG, 2001, Berlin, Germany, March 26-28, 2001 (archive: CFP, poster, program).
  Special issue in CGTA, Volume 25, Issues 1-2 (May 2003).
• 16th EuroCG, 2000, Eilat, Israel, March 13-15, 2000 (archive: program, abstracts).
  Special issue in CGTA, Volume 21, Issues 1-2 (January 2002).
• 15th EuroCG, 1999, Antibes, France, March 15-17, 1999 (archive: CFP, accepted)
• 14th EuroCG, 1998, Barcelona, Spain, March 26-27, 1998 (archive: program)
  Special issue in Discrete Applied Mathematics, Volume 109, Issues 1-2, Pages 1-196 (15 April 2001).
• 13th EuroCG, 1997, Wuerzburg, Germany, March 20-21, 1997 (archive: program+abstracts)
  Special issue in Discrete Applied Mathematics, Volume 93, Issue 1, Pages 1-140 (15 April 1999).
• 12th EuroCG, 1996, Münster, Germany, March 28-29, 1996 (archive: CFP, program)
• 11th EuroCG, 1995, Linz, Austria
• 10th EuroCG, 1994, Santander, Spain, March 17-18, 1994.
• 9th EuroCG, 1993, Hagen, Germany, March 18-19, 1993.
• 8th EuroCG, 1992, Utrecht, The Netherlands, March 12-13, 1992 (abstracts in one big pdf)
• 7th EuroCG, 1991, Bern, Switzerland, March 21-22, 1991. LNCS volume 553
• 6th EuroCG, 1990, Siegen, Germany
• 5th EuroCG, 1989, Freiburg, Germany
• 4th EuroCG, 1988, Würzburg, Germany, March 24-25, 1988. LNCS volume 333
• 3rd EuroCG, 1985, Karlsruhe, Germany
• 2nd EuroCG, 1984, Bern, Switzerland
• 1st EuroCG, 1983, Zürich, Switzerland

Topics:

 Circles and Spheres

 Coloring

 Compass and Straightedge

 Combinatorial Geometry

 Covering and Packing

 Dissection

 Fractals

 Geometric Models

 Geometric Topology

 Hyperbolic Geometry

 Knot Theory

 Lattice Theory and Geometry of Numbers

 Nearest Neighbors and Voronoi Diagrams

 Origami

 Pentagonal Geometry and the Golden Ratio

 Polyhedra and Polytopes

 Randomness and Geometric Probability

 Rectilinear Geometry

 Spirals

 Symmetry and Group Theory

 Tiling

 Triangles and Simplices

 Width, Diameter, and Geometric Inequalities

 Planar Geometry

 Three-dimensional Geometry

 Many-dimensional Geometry

 Open Problems

 Lesson Plans and Teaching Materials

 Software and Animations

 Miscellanous

CCCG 2010 Proceedings CCCG 2009 Proceedings CCCG 2008 Proceedings CCCG 2007 Proceedings CCCG 2006 Proceedings CCCG 2005 Proceedings CCCG 2004 Proceedings CCCG 2003 Proceedings CCCG 2002 Proceedings CCCG 2001 Proceedings CCCG 2000 Proceedings

CCCG 1999 Proceedings CCCG 1998 Proceedings CCCG 1997 Proceedings CCCG 1996 Proceedings CCCG 1995 Proceedings (In Progress) CCCG 1994 Proceedings CCCG 1993 Proceedings CCCG 1992 Proceedings CCCG 1991 Proceedings CCCG 1990 Proceedings CCCG 1989 Proceedings

Upcoming Conferences

CCCG 2012 in Charlottetown, Prince Edward Island
CCCG 2011 in Toronto, Ontario

Previous Conferences

CCCG 2010 in Winnipeg, Manitoba CCCG 2009 in Vancouver, British Columbia CCCG 2008 in Montreal, Quebec CCCG 2007 in Ottawa, Ontario CCCG 2006 in Kingston, Ontario CCCG 2005 in Windsor, Ontario CCCG 2004 in Montreal, Quebec CCCG 2003 in Halifax, Nova Scotia CCCG 2002 in Lethbridge, Alberta CCCG 2001 in Waterloo, Ontario CCCG 2000 in Fredericton, New Brunswick

CCCG 1999 in Vancouver, British Columbia CCCG 1998 in Montreal, Quebec CCCG 1997 in Kingston, Ontario CCCG 1996 in Ottawa, Ontario CCCG 1995 in Quebec City, Quebec CCCG 1994 in Saskatoon, Saskatchewan CCCG 1993 in Waterloo, Ontario CCCG 1992 in St. John's, Newfoundland CCCG 1991 in Burnaby, British Columbia CCCG 1990 in Ottawa, Ontario CCCG 1989 in Montreal, Quebec