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.
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$.
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$.
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.
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)$.
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.
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.
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$.
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})$.