GAIA Workshop on Space-filling curves and applications
A mini-course by Herman Haverkort in KAIST
Space-filling curves are infinitely long curves that completely fill a higher-dimensional region, such as a square, a cube, or a tetrahedron. Such curves can be used to define linear orderings or traversal orders of points or objects in higher-dimensional spaces: we simply visit the objects in the order in which they appear along the curve. In this lecture series, we will discuss different types of space-filling curves and their distinctive properties, and we discuss how ordering objects along a well-chosen space-filling curve can help us speed up various computations.
Lectures
Lecture 1. Lebesgue's curve.
May 9, 16:00~17:00, Classroom #3, Building E3-1.
Space-filling curves. Continuous versus discrete space-filling curves. Lebesgue's curve and Morton indexing. Conversion between Morton index and workspace coordinates. Applications to matrix operations, processing of digital elevation models, triangulations and map overlay.
Lecture 2. Hilbert's curve.
May 9, 17:00~18:00, Classroom #3, Building E3-1.
Hilbert's curve. Drawing a sketch of the Hilbert curve. Comparing the position of two points along the curve. Locality-preserving properties (dilation, bounding-box quality). Higher-dimensional Hilbert curves. Applications to range queries, nearest-neighbour queries, outlier identification, and image processing.
Lecture 3. Peano's curve.
May 10, 11:00~12:00, Room 1101, Building E3-1.
Peano's square-filling and cube-filling curves. Partitioning quality properties (surface-to-volume ratio) and symmetry properties. Application to optimizing load balancing, inter-processor communication and cache utilization in scientific computing.
Lecture 4. Sierpinski's curve.
May 10, 12:00~13:00, Room 1101, Building E3-1.
Sierpinski's curve. Analysis of the dilation of the Sierpinski curve. Dilation lower bounds: results, open questions and conjectures. Tetrahedron-filling curves. Adaptive curves and applications to mesh processing.
Lecture 5. Gosper's curve.
May 10, 15:00~16:00, Room 1101, Building E3-1.
Constructing recursive tessellations. Gosper's flowsnake. Applications to graph drawing and to storage of hexagonal grids. Fragmentation measures (Arrwwid numbers). Arrwwid number lower bounds and open questions about recursive tessellations in 2D and 3D.
Lecture 6. More curves.
May 10, 16:00~17:00, Room 1101, Building E3-1.
Composite curves: Beta-Omega curve, rectangle-filling curves. Peano variants: coil curve, R-curve. Interdimensionally-consistent curves, and possible applications to range queries. Wrap-up.
Herman Haverkort
Herman Haverkort received his PhD degree from the computer science department of Utrecht University, the Netherlands, in 2004, on a thesis on geometric networks and data structures. He subsequently worked as a post-doctoral researcher in the computer science departments of the Karlsruhe Institute of Technology, Germany, and Aarhus University, Denmark. Since 2005 he has been an assistant professor in the Eindhoven University of Technology, the Netherlands. His research is mainly concerned with algorithms for geographic information systems (computations on elevation models, cartography); theory and applications of recursive tilings and space-filling curves; and practical external-memory algorithms and data structures.
You can find out more about his research on space-filling curves.
- Contact : Prof. Otfried Cheong (KAIST, otfried@kaist.airpost.net)
