Invited Speakers

Triangulations in CGAL:
To Non-Euclidean Spaces... and Beyond!

Monique Teillaud (INRIA Nancy - Grand Est, LORIA, France)

The talk will review some of the basic ideas underlying the design of the classic triangulation packages in CGAL. Then it will present more recent work on the computation of Delaunay triangulations of some flat tori and of the Bolza surface, and show how the CGAL basic ideas could be extended. Triangulations are known to have many applications. The talk will exhibit concrete uses of the various CGAL triangulation packages. Finally, future work and its motivation will be mentioned.

Biography

Former student of the École Normale Supérieure in Paris, holder of an Agrégation in Mathematics and a PhD in Computer Science ("Towards dynamic randomized algorithms in computational geometry"). Managing Editor of JoCG (the free and gratis Journal of Computational Geometry), PC Chair of SoCG'08, Chair of the Computational Geometry Steering Committee since 2016.
Monique Teillaud has been involved in the CGAL project since the end of the 90's. She has co-authored several packages in the library. Her research has focused on computing triangulations in non-Euclidean spaces for more than ten years.

The Saga of the Skyline Points

Otfried Cheong (SCALGO, Denmark, and KAIST, South Korea)

Skyline points or non-dominated points in a database are those points that are "best" in at least one of their attributes. In spatial databases, interesting implicit attributes are the distances to a given set of sites of interest. We present some history of the problem, and then show how computational geometry helps to transform it into a question about certain Voronoi diagrams with additive weights and a convex-distance function. Finally, we show how to solve the problem for n data points and m sites of interest in time O((n+m) log (n+m)), improving on all previous results that require time proportial to nm.

Biography

Otfried Cheong received his Ph.D. at FU Berlin in 1992. After holding positions at Utrecht University, Postech, Hong Kong University of Science & Technology, and TU Eindhoven, he has been at KAIST since 2005. He is on the editorial board of 'Discrete & Computational Geometry' and 'Computational Geometry: Theory & Applications', and was elected an ACM Distinguished Scientist in 2016. He is currently on leave from KAIST to work with Scalgo on water flow simulations.

Location & Information

Maarten Löffler (Utrecht University, The Netherlands)

Let P be a set of n points in the plane. In the traditional geometric algorithms view, P is given as an unordered sequence of locations (usually pairs of x and y coordinates). There are many interesting and useful structures that one can build on top of P: the Delaunay triangulation, Voronoi diagram, well-separated pair decomposition, quadtree, etc. These structures can all be represented in O(n) space but take Ω(n log n) time to construct on a Real RAM, and, hence, contain information about P that is encoded in P but cannot be directly read from P.

In this talk I will explore the question how much information about the structure of a set of points can be derived from their locations, especially when we are uncertain about the precise locations of the points.

Biography

Maarten Löffler is currently an assistant professor at Utrecht University. He has been a post-doc researcher at the Bren School of information and computer sciences of the University of California, Irvine. He was a PhD-student at Utrecht University.

Quantifying Shape Using the Medial Axis

Erin Wolf Chambers (Saint Louis University, USA)

The medial axis plays a fundamental role in shape matching and analysis, but is widely known to be unstable to even small boundary perturbations. Methods for pruning the medial axis are usually guided by some measure of significance, with considerable work done for both 2- and 3-dimensional shapes. Such significance measures can be used for identifying salient features, and hence are useful for simplification, comparison, and alignment. In this talk, we will present theoretical insights and properties of commonly used significance measures, focusing on those in 2D and 3D that are both shape-revealing and topology-preserving, as well as being robust to noise on the boundary. We'll also discuss more recent work in progress on using such measures to de-noise a shape and identify topologically and geometrically prominent features. Finally, we will cover several applications of these measures and techniques to real-world data sets.

Biography

Dr. Erin Wolf Chambers is a Professor at Saint Louis University in the Department of Computer Science, with a secondary appointment in the Department of Mathematics. Her research focus is on computational topology and geometry, with a more general interest in combinatorics and combinatorial algorithms. Complementing this work, she is also active in research projects to support and improve the culture and climate in computer science and mathematics, as well as to try to improve broader STEM educational experiences at all levels. She serves on the Computational Geometry Steering Committee and the Women in Computational Topology Steering Committee, as well as being an editor for Journal of Computational Geometry and for the Journal of Applied and Computational Topology. She received her PhD in Computer Science from the University of Illinois at Urbana-Champaign in 2008, and was a Visiting Research Professor at Saarland University in summer 2011.