Simple and practical algorithms in computational geometry

Robson, Eliot Wong

Permalink

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

Description

Title

Simple and practical algorithms in computational geometry

Author(s)

Robson, Eliot Wong

Issue Date

2025-07-14

Director of Research (if dissertation) or Advisor (if thesis)

Har-Peled, Sariel

Doctoral Committee Chair(s)

Har-Peled, Sariel

Committee Member(s)

• Amato, Nancy
• Driemel, Anne
• Erickson, Jeff

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Geometry
• algorithms

Abstract

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.

Graduation Semester

2025-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Eliot Wong Robson

Owning Collections