Twenty questions with a random liar
I have another new arXiv preprint: “Computational geometry with probabilistically noisy primitive operations”, arXiv:2501.07707, with Mike Goodrich and his student Vinesh Sridhar. Many computational geometry algorithms are designed around the use of primitives, subroutines that access the coordinate data of the input and convert it into combinatorial information, with the assumption that all access to the input goes through these primitives. For instance, a key primitive often used for computing convex hulls (and central to my book on forbidden configurations) takes as input an ordered triple of points in the plane and determines whether they are ordered clockwise around the triangle they generate, counterclockwise, or collinear. The premise of the new preprint is that this primitive could randomly produce the wrong result, with some constant probability, independent of any past errors or successes.
(The title of this post comes from a related paper by Dhagat, Gács, and Winkler, from SODA 1992, using a different model in which the primitive is incorrect adversarially rather than randomly.)
