4 papers · 1 filter
Optimal Parallel Algorithms for Convex Hulls in 2D and 3D under Noisy Primitive Operations
Michael T. Goodrich, Vinesh Sridhar
In the noisy primitives model, each primitive comparison performed by an algorithm, e.g., testing whether one value is greater than another, returns the incorrect answer with rando…
Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction
Shion Fukuzawa, Michael T. Goodrich, Sandy Irani
We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a…
Computational Geometry with Probabilistically Noisy Primitive Operations
David Eppstein, Michael T. Goodrich, Vinesh Sridhar
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 approa…
Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
Michael T. Goodrich, Ryuto Kitagawa
In this paper, we present Ray-shooting Quickhull, which is a simple, randomized, outputsensitive version of the Quickhull algorithm for constructing the convex hull of a set of n p…