5 papers
Exact Learning of Weighted Graphs Using Composite Queries
Michael T. Goodrich, Songyu Liu, Ioannis Panageas
In this paper, we study the exact learning problem for weighted graphs, where we are given the vertex set, , of a weighted graph, , but we are not given . The prob…
Parallel Joinable B-Trees in the Fork-Join I/O Model
Michael Goodrich, Yan Gu, Ryuto Kitagawa +1
Balanced search trees are widely used in computer science to efficiently maintain dynamic ordered data. To support efficient set operations (e.g., union, intersection, difference)…
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…