{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129873"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129873","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Simple and practical algorithms in computational geometry","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","abstract_has_math":false,"creators":["Robson, Eliot Wong"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Har-Peled, Sariel","Amato, Nancy","Driemel, Anne","Erickson, Jeff"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-07-14","date_published":"2025-07-14","updated_at":"2026-07-22T22:25:06Z","subjects":["Geometry","Algorithms"],"languages":["en","eng"],"rights":["Copyright 2025 Eliot Wong Robson"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129873","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Har-Peled, Sariel","Amato, Nancy","Driemel, Anne","Erickson, Jeff"]},{"key":"dc:creator","label":"Author","values":["Robson, Eliot Wong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-07-14","2025-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Geometry","Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Eliot Wong Robson"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129873"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","The student, Eliot Robson, accepted the attached license on 2025-07-14 at 09:47.","The student, Eliot Robson, submitted this Dissertation for approval on 2025-07-14 at 10:02.","This Dissertation was approved for publication on 2025-07-14 at 11:36.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22542 on 2025-10-20 at 16:57:54","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Simple and practical algorithms in computational geometry"]}]}],"canonical_facts":{"dc:contributor":["Har-Peled, Sariel","Amato, Nancy","Driemel, Anne","Erickson, Jeff"],"dc:creator":["Robson, Eliot Wong"],"dc:date":["2025-07-14","2025-08"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","The student, Eliot Robson, accepted the attached license on 2025-07-14 at 09:47.","The student, Eliot Robson, submitted this Dissertation for approval on 2025-07-14 at 10:02.","This Dissertation was approved for publication on 2025-07-14 at 11:36.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22542 on 2025-10-20 at 16:57:54","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129873"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Eliot Wong Robson"],"dc:subject":["Geometry","Algorithms"],"dc:title":["Simple and practical algorithms in computational geometry"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:06Z"}