Geometric problems in higher dimensions: Voronoi diagrams, the Fermat point, and the bichromatic discrepancy

Decanato - Facoltà di scienze informatiche

Data: 18 Maggio 2022 / 14:30 - 16:30

USI Campus EST, room C1.04, Sector C // Online on MS Teams

You are cordially invited to attend the PhD Dissertation Defence of Martin Suderland on Wednesday 18 May 2022 at 14:30 in room C1.04 (Campus EST) or online on MS Teams.

Research in computational geometry has produced many results in the plane and low dimensional spaces. These include impossibility and complexity results, efficient data structures and optimal algorithms. In higher dimensions the situation is quite different and such results are more sparse. We consider three such problems. 1) We study the order-k Voronoi diagram of lines, line segments and convex polyhedra under Euclidean and polyhedral distances. We derive properties and complexity bounds for the diagram and its unbounded features. In case of the farthest Voronoi diagram, we also discuss optimal time algorithms for deriving the unbounded features in the Euclidean version and for constructing the complete diagram when the polyhedral distances are used. 2) We propose several algorithms for computing epsilon-approximations of the Fermat point based on subdivision methods. We put an emphasis on robustness derived through soft predicates and interval arithmetic. We use similar techniques to derive approximations of n-ellipses in the plane. Our implementation and experiments suggest practicability of the proposed methods. 3) We introduce a new concept called bichromatic discrepancy. It deals with the question of how uniformly points of two colors can be distributed in the unit square. We derive a lower bound for this bichromatic discrepancy and also describe point sets, which induce a small discrepancy. An application of this new concept to digitalizing Euclidean segments is pointed out.

Dissertation Committee:
- Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Piotr Krzysztof Didyk, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Kai Hormann, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Gill Barequet , Technion, Israel (External Member)
- Prof. Chee Yap, New York University (External Member)