Home

Otfried Cheong

  1. The Cost of Bounded Curvature.

    Wed, 11/23/2011 - 15:01 — SomNambul
    Authors: Otfried Cheong, Hyo-Sil Kim
    Subjects: Computational Geometry
    Abstract

    We study the motion-planning problem for a car-like robot whose turning
    radius is bounded from below by one and which is allowed to move in the forward
    direction only (Dubins car). For two robot configurations $\sigma, \sigma'$,
    let $\ell(\sigma, \sigma')$ be the shortest bounded-curvature path from
    $\sigma$ to $\sigma'$. For $d \geq 0$, let $\ell(d)$ be the supremum of
    $\ell(\sigma, \sigma')$, over all pairs $(\sigma, \sigma')$ that are at
    Euclidean distance $d$.

  2. Lines pinning lines.

    Thu, 02/18/2010 - 16:01 — SomNambul
    Authors: Otfried Cheong, Xavier Goaoc, Boris Aronov, Günter Rote
    Subjects: Metric Geometry
    Abstract

    A line g is a transversal to a family F of convex polytopes in 3-dimensional
    space if it intersects every member of F. If, in addition, g is an isolated
    point of the space of line transversals to F, we say that F is a pinning of g.
    We show that any minimal pinning of a line by convex polytopes such that no
    face of a polytope is coplanar with the line has size at most eight. If, in
    addition, the polytopes are disjoint, then it has size at most six. We
    completely characterize configurations of disjoint polytopes that form minimal
    pinnings of a line.

  3. Farthest-Polygon Voronoi Diagrams.

    Thu, 01/21/2010 - 16:01 — SomNambul
    Authors: Joachim Gudmundsson, Otfried Cheong, Hazel Everett, Marc Glisse, Samuel Hornus, Sylvain Lazard, Mira Lee, Hyeon-Suk Na
    Subjects: Computational Geometry
    Abstract

    Given a family of k disjoint connected polygonal sites in general position
    and of total complexity n, we consider the farthest-site Voronoi diagram of
    these sites, where the distance to a site is the distance to a closest point on
    it. We show that the complexity of this diagram is O(n), and give an O(n log^3
    n) time algorithm to compute it. We also prove a number of structural
    properties of this diagram. In particular, a Voronoi region may consist of k-1
    connected components, but if one component is bounded, then it is equal to the
    entire region.

  4. Set Systems and Families of Permutations with Small Traces.

    Wed, 12/16/2009 - 16:01 — SomNambul
    Authors: Otfried Cheong, Xavier Goaoc, Cyril Nicaud
    Subjects: Computational Geometry
    Abstract

    We study the maximum size of a set system on $n$ elements whose trace on any
    $b$ elements has size at most $k$. We show that if for some $b \ge i \ge 0$ the
    shatter function $f_R$ of a set system $([n],R)$ satisfies $f_R(b) <
    2^i(b-i+1)$ then $|R| = O(n^i)$; this generalizes Sauer's Lemma on the size of
    set systems with bounded VC-dimension. We use this bound to delineate the main
    growth rates for the same problem on families of permutations, where the trace
    corresponds to the inclusion for permutations.

  5. On Finding Non-dominated Points using Compact Voronoi Diagrams.

    Mon, 09/07/2009 - 22:13 — SomNambul
    Authors: Binay Bhattacharya, Arijit Bishnu, Otfried Cheong, Sandip Das, Arindam Karmakar, Jack Snoeyink
    Subjects: Computational Geometry
    Abstract

    We discuss in this paper a method of finding skyline or non-dominated points
    in a set $P$ of $n_P$ points with respect to a set $S$ of $n_S$ sites. A point
    $p_i \in P$ is non-dominated if and only if for each $p_j \in P$, $j \not= i$,
    there exists at least one point $s \in S$ that is closer to $p_i$ than $p_j$.
    We reduce this problem of determining non-dominated points to the problem of
    finding sites that have non-empty cells in an additive Voronoi diagram with a
    convex distance function.

Math-arch

Syndicate content