Hot News‎ > ‎

GAIA Workshop on Space Tesselation and Packing

posted Dec 12, 2017, 6:23 PM by Eunyoung Choi   [ updated Dec 12, 2017, 10:23 PM ]
GAIA Workshop on Space Tesselation and Packing
                                                                KAIST, Sep. 14 ~ 17, 2017 

  Objective :
A Voronoi diagram is a tessellation of space into regions based on the distance to a specific subset of the space. Voronoi diagrams arise in nature and have practical and theoretical applications in many fields of science, including biology, polymer physics and informatics. They have been extensively studied in computational geometry for point sites and the Euclidean metric in two dimensions. Voronoi diagrams can be defined for sites other than points, metrics other than Euclidean, and dimensions higher than 2-dimension. For instance, the retraction method used in robot motion planning uses convex distance functions and the autonomous robot navigations find clear routes in the Voronoi diagrams of walls (or obstacles) of the room. POI sites in a city are amidst obstacles (buildings, rivers, etc) and transportation networks (roads, railways). It is not clear how to generalize known results to more general sites under general metrics in 2-or higher dimensions. More research is needed to handle more general Voronoi diagrams.

Packing is a classical geomeric optimization problem in which the shape of a container is predefined (such as a disk, a square, or a rectangle) and we aim to find a smallest container for input objects while the input objects remain disjoint in their interiors. Packing problems have been studied for a long time. It dates back to 1611 when Kepler studied sphere packing in three-dimensional Euclidean space. There has been recent algorithmic progress on packing problem - packing a set of disks into a smallest disk and packing a set of convex polygons into a given axis-parallel rectangle under translations and rigid motions in the plane. There still are, however, many packing problems for more general objects under various transformations in higher dimensions.

There are many other optimization problems in space tessellation and packing. This meeting serves to trigger extensive collaboration on advanced research in this area.

- Organizers: Otfried Cheong(KAIST), Hee-Kap Ahn(POSTECH),  Christian Knauer(University of Bayreuth)
- Participants

Till Miltzow(Université Libre de Bruxelles), Herman Haverkort(TU Eindhoven),

Antoine Vigneron(UNIST), Fabian Stehn(University of Bayreuth), Siu-Wing Cheng(HKUST),

Xavier Goaoc(University of Marne-la-Vallée), Hyung-Chan An(Yonsei University),

Eunjung Kim(LAMSADE, CNRS), Raimund Seidel(Saarland University),

Yoshio Okamoto(University of Electro-Communications), Zuzana Patáková(Charles University),

Sangduk Yoon(POSTECH), Eunjin Oh(POSTECH), Édouard Bonnet(Middlesex University),

Taegyoung Lee(KAIST), Yoonsung Choi(KAIST)