2026-07-23T04:52:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24255 2025-11-12T13:39:29Z ddc:004 open_access

Computational Geometry with Probabilistically Noisy Primitive Operations Eppstein, David Goodrich, Michael T. Sridhar, Vinesh Computational geometry noisy comparisons random walks Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Eppstein and Michael T. Goodrich and Vinesh Sridhar 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.24 urn:nbn:de:0030-drops-242552 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.24 eng https://creativecommons.org/licenses/by/4.0/legalcode