Minghui Jiang

  1. Sweeping an oval to a vanishing point.

    Authors: Adrian Dumitrescu, Minghui Jiang
    Subjects: Computational Geometry
    Abstract

    Given a convex region in the plane, and a sweep-line as a tool, what is best
    way to reduce the region to a single point by a sequence of sweeps? The problem
    of sweeping points by orthogonal sweeps was first studied in [2]. Here we
    consider the following \emph{slanted} variant of sweeping recently introduced
    in [1]: In a single sweep, the sweep-line is placed at a start position
    somewhere in the plane, then moved continuously according to a sweep vector
    $\vec v$ (not necessarily orthogonal to the sweep-line) to another parallel end
    position, and then lifted from the plane.

  2. Coloring translates and homothets of a convex body.

    Authors: Adrian Dumitrescu, Minghui Jiang
    Subjects: Discrete Mathematics
    Abstract

    We obtain improved upper bounds and new lower bounds on the chromatic number
    as a linear function of the clique number, for the intersection graphs (and
    their complements) of finite families of translates and homothets of a convex
    body in $\RR^n$.

  3. Opaque sets.

    Authors: Adrian Dumitrescu, János Pach, Minghui Jiang
    Subjects: Computational Geometry
    Abstract

    The problem of finding ``small'' sets that meet every straight-line which
    intersects a given convex region was initiated by Mazurkiewicz in 1916. We call
    such a set an {\em opaque set} or a {\em barrier} for that region. We consider
    the problem of computing the shortest barrier for a given convex polygon with
    $n$ vertices. For general barriers, we present a simple $O(n)$ time
    approximation algorithm with ratio $\frac{1}{2}+ \frac{2
    +\sqrt{2}}{\pi}=1.5867\ldots$.

  4. The zero exemplar distance problem.

    Authors: Minghui Jiang
    Subjects: Computational Complexity
    Abstract

    Blin, Fertin, Sikora, and Vialette recently proved that deciding whether the
    exemplar distance between two genomes with duplicate genes is zero is NP-hard
    even if each gene appears at most two times in each genome. We give an
    alternative proof of this remarkable result.

  5. New bounds on the average distance from the Fermat-Weber center of a planar convex body.

    Authors: Adrian Dumitrescu, Minghui Jiang, Csaba D. Tóth
    Subjects: Metric Geometry
    Abstract

    The Fermat-Weber center of a planar body $Q$ is a point in the plane from
    which the average distance to the points in $Q$ is minimal. We first show that
    for any convex body $Q$ in the plane, the average distance from the
    Fermat-Weber center of $Q$ to the points of $Q$ is larger than ${1/6} \cdot
    \Delta(Q)$, where $\Delta(Q)$ is the diameter of $Q$. This proves a conjecture
    of Carmi, Har-Peled and Katz. From the other direction, we prove that the same
    average distance is at most $\frac{2(4-\sqrt3)}{13} \cdot \Delta(Q) < 0.3490
    \cdot \Delta(Q)$.

  6. Inapproximability of maximal strip recovery.

    Authors: Minghui Jiang
    Subjects: Computational Complexity
    Abstract

    In comparative genomic, the first step of sequence analysis is usually to
    decompose two or more genomes into syntenic blocks that are segments of
    homologous chromosomes. For the reliable recovery of syntenic blocks, noise and
    ambiguities in the genomic maps need to be removed first. Maximal Strip
    Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff
    for reliably recovering syntenic blocks from genomic maps in the midst of noise
    and ambiguities.

  7. Dispersion in unit disks.

    Authors: Adrian Dumitrescu, Minghui Jiang
    Subjects: Computational Geometry
    Abstract

    We present two new approximation algorithms with (improved) constant ratios
    for selecting $n$ points in $n$ unit disks such that the minimum pairwise
    distance among the points is maximized.

    (I) A very simple $O(n \log{n})$-time algorithm with ratio 0.5110 for
    disjoint unit disks. In combination with an algorithm of Cabello \cite{Ca07},
    it yields a $O(n^2)$-time algorithm with ratio of 0.4487 for dispersion in $n$
    not necessarily disjoint unit disks.

  8. Piercing translates and homothets of a convex body.

    Authors: Adrian Dumitrescu, Minghui Jiang
    Subjects: Computational Geometry
    Abstract

    According to a classical result of Gr\"unbaum, the transversal number
    $\tau(\F)$ of any family $\F$ of pairwise-intersecting translates or homothets
    of a convex body $C$ in $\RR^d$ is bounded by a function of $d$. Denote by
    $\alpha(C)$ (resp. $\beta(C)$) the supremum of the ratio of the transversal
    number $\tau(\F)$ to the packing number $\nu(\F)$ over all families $\F$ of
    translates (resp. homothets) of a convex body $C$ in $\RR^d$.

  9. On the largest empty axis-parallel box amidst $n$ points.

    Authors: Adrian Dumitrescu, Minghui Jiang
    Subjects: Computational Geometry
    Abstract

    We give the first nontrivial upper and lower bounds on the maximum volume of
    an empty axis-parallel box inside an axis-parallel unit hypercube in $\RR^d$
    containing $n$ points. For a fixed $d$, we show that the maximum volume is of
    the order $\Theta(\frac{1}{n})$.

Syndicate content