Publications with Vinesh Sridhar
- Computational geometry with probabilistically noisy primitive operations.
D. Eppstein, M. T. Goodrich, and V. Sridhar.
arXiv:2501.07707.
Proc. 19th Algorithms and Data Structures Symposium (WADS 2025).
Leibniz International Proceedings in Informatics (LIPIcs) 349, 2025, pp. 24:1–24:20.
An algorithm that uses Boolean primitive operations, like comparisons, that may be erroneous with some small independent probability per call, may be made to run correctly with high probability by repeating each primitive enough times to be sure its majority result is correct, but this incurs a logarithmic time penalty. Prior work avoids this penalty for sorting; we extend this speedup to algorithms in computational geometry that can be formulated using path search in DAGs. Applications of our "path-guided pushdown random walk" technique include point location, plane sweep, convex hulls, and Delaunay triangulation.