Back
2022INF005
Doctoral thesis

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

  • 2022

PhD: Università della Svizzera italiana

Voronoi diagram
Order-k
Farthest
Generalised sites
Convex polyhedral
Higher dimensions
Fermat point
Weber point
N-ellipse
Approximation
Bichromatic discrepancy
Consistent digital rays
English 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.
Collections
Language
  • English
Classification
Computer science and technology
License
License undefined
Open access status
green
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1321069
Statistics
Document views: 65 File downloads:
  • 2022INF005.pdf: 172