Simple and practical algorithms in computational geometry

Geometric data is everywhere, and the sheer size of modern datasets motivates the development of efficient geometric algorithms. This thesis investigates several such algorithms – striving for near linear time and practical simplicity. The specific problems studied in this thesis include: 1. No-dimensional Tverberg partitions: We study a relaxation of the classical Tverberg theorem, where the intersection requirement is weakened, and the dependence on the dimension is replaced by other parameters. We present simple linear-time algorithms for computing such partitions, improving over known results that were either existential, or yield worse partitions. 2. Constructing a reliable spanner for disk graphs: We present a near-linear time algorithm for computing connectivity-preserving “spanners” for disk intersection graphs that can withstand catastrophic failures, where a large fraction of disks fail/disappear. 3. Fault-tolerant k-center. We consider a robust variant of k-center clustering where some centers could fail. This is done by measuring the distance for each client to the αth closest center (instead of the closest). We establish an analogous connection between this (k, α)- center problem and the α-distance permutation, similar to the established link between the traditional k-center problem and the greedy permutation. We provide efficient approximation algorithms for computing this clustering and its associated α-distance permutation. 4. Practical Fr´echet distance. We present simple algorithms for the Fr´echet distance, a metric that quantifies the similarity between two polygonal curves. Combining simplification, approximation, and a new variant of the Fr´echet distance, we present new algorithms for computing the almost-exact Fr´echet distance between curves, that in practice seems to run in near linear time. The new implementation is faster than the current state-of-the-art. We provide open-source implementations both in Julia and Python.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Robson, Eliot Wong

Contributors dc:contributor

• Har-Peled, Sariel
• Amato, Nancy
• Driemel, Anne
• Erickson, Jeff

• Geometry
• Algorithms

Statement dc:rights

• Copyright 2025 Eliot Wong Robson

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129873

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129873