Now showing items 1-3 of 3
Geometric dilation of closed planar curves: a new lower bound [Presentation]
Given any simple closed curve C in the Euclidean plane, let w and D denote the minimal and the maximal caliper distances of C, correspondingly. We show that any such curve C has a geometric dilation of at least arcsin( ...
Space-efficient geometric divide-and-conquer algorithms [Presentation]
We present an approach to simulate divide-and-conquer algorithms in a space-efficient way, and illustrate it by giving space-efficient algorithms for the closest-pair, bichromatic closest-pair, all-nearest-neighbors, and ...
Similarity search in semialgebraic pattern spaces [Presentation]
We describe a general technique to construct data structures for similarity search in semialgebraic pattern spaces. These spaces capture most known combinations of geometric patterns (e.g., point sets, polygons, polygonal ...