## Search

Now showing items 1-10 of 56

#### Curvature criteria to fit curves to discrete data [Presentation]

(2004)

Several geometric criteria to fit a polygonal closed curve to discrete two-dimensional data are considered and analysed. Most of these criteria are related to the concept of curvature, for example, one criterion is ...

#### Space-efficient geometric divide-and-conquer algorithms [Presentation]

(2004)

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 ...

#### On relative isodiametric inequalities [Presentation]

(2004)

We consider subdivisions of convex bodies G in two subsets E and G\E. We obtain several inequalities comparing the relative volume 1) with the minimum relative diameter and 2) with the maximum relative diameter. In the ...

#### 3D realization of two triangulations of a onvex polygon [Presentation]

(2004)

We study the problem of construction of a convex 3-polytope whose (i) shadow boundary has n vertices and (ii) two hulls, upper and lower, are isomorphic to two given triangulations of a convex n-gon. Barnette [℄ D. W. ...

#### Finding planar regions in a terrain [Presentation]

(2004)

We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic ...

#### Finding a widest empty 1-corner corridor [Presentation]

(2004)

Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We star giving a characterization of the 1-corner corridors that we call locally widest. Our approach to finding ...

#### Geometric dilation of closed planar curves: a new lower bound [Presentation]

(2004)

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( ...

#### Computing the convex hull of disks using only their chirotope [Presentation]

(2004)

We show that the convex hull of a collection of n pairwise disjoint disks in the plane is computable in O(n log n) time using only the chirotope of the collection of disks. The method relies mainly on the development of ...

#### Maximizing the area of overlap of two unions of disks under rigid motion [Presentation]

(2004)

Let A and B be two sets of n resp. m (m ≥ n) disjoint unit disks in the plane. We consider the problem of finding a rigid motion of A that maximizes the total area of its overlap with B. The function describing the area ...