
We say that a finite set of red and blue points in the plane in general
position can be $K_{1,3}$covered if the set can be partitioned into subsets of
size $4$, with $3$ points of one color and $1$ point of the other color, in
such a way that, if at each subset the fourth point is connected by
straightline segments to the samecolored points, then the resulting set of
all segments has no crossings. We consider the following problem: Given a set
$R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in general
position, how many points of $R\cup B$ can be $K_{1,3}$covered? and we prove
the following results:
(1) If $r=3g+h$ and $b=3h+g$, for some nonnegative integers $g$ and $h$,
then there are point sets $R\cup B$, like $\{1,3\}$equitable sets (i.e.,
$r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$covered.
(2) If $r=3g+h$, $b=3h+g$ and the points in $R\cup B$ are in convex position,
then at least $r+b4$ points can be $K_{1,3}$covered, and this bound is tight.
(3) There are arbitrarily large point sets $R\cup B$ in general position,
with $r=b+1$, such that at most $r+b5$ points can be $K_{1,3}$covered.
(4) If $b\le r\le 3b$, then at least $\frac{8}{9}(r+b8)$ points of $R\cup B$
can be $K_{1,3}$covered. For $r>3b$, there are too many red points and at
least $r3b$ of them will remain uncovered in any $K_{1,3}$covering.
Furthermore, in all the cases we provide efficient algorithms to compute the
corresponding coverings.

Let $S$ be a set of $n$ points in general position in the plane, $r$ of which
are red and $b$ of which are blue. In this paper we prove that there exist: for
every $\alpha \in \left [ 0,\frac{1}{2} \right ]$, a convex set containing
exactly $\lceil \alpha r\rceil$ red points and exactly $\lceil \alpha b \rceil$
blue points of $S$; a convex set containing exactly $\left \lceil
\frac{r+1}{2}\right \rceil$ red points and exactly $\left \lceil
\frac{b+1}{2}\right \rceil$ blue points of $S$. Furthermore, we present
polynomial time algorithms to find these convex sets. In the first case we
provide an $O(n^4)$ time algorithm and an $O(n^2\log n)$ time algorithm in the
second case. Finally, if $\lceil \alpha r\rceil+\lceil \alpha b\rceil$ is
small, that is, not much larger than $\frac{1}{3}n$, we improve the running
time to $O(n \log n)$.

We consider the Minimum Coverage Kernel problem: given a set B of
$d$dimensional boxes, find a subset of B of minimum size covering the same
region as B. This problem is $\mathsf{NP}$hard, but as for many
$\mathsf{NP}$hard problems on graphs, the problem becomes solvable in
polynomial time under restrictions on the graph induced by $B$. We consider
various classes of graphs, show that Minimum Coverage Kernel remains
$\mathsf{NP}$hard even for severely restricted instances, and provide two
polynomial time approximation algorithms for this problem.

We consider a natural notion of search trees on graphs, which we show is
ubiquitous in various areas of discrete mathematics and computer science.
Search trees on graphs can be modified by local operations called rotations,
which generalize rotations in binary search trees. The rotation graph of search
trees on a graph $G$ is the skeleton of a polytope called the graph
associahedron of $G$.
We consider the case where the graph $G$ is a tree. We construct a family of
trees $G$ on $n$ vertices and pairs of search trees on $G$ such that the
minimum number of rotations required to transform one search tree into the
other is $\Omega (n\log n)$. This implies that the worstcase diameter of tree
associahedra is $\Theta (n\log n)$, which answers a question from Thibault
Manneville and Vincent Pilaud. The proof relies on a notion of projection of a
search tree which may be of independent interest.

We study the cyclic color sequences induced at infinity by colored rays with
apices being a given balanced finite bichromatic point set. We first study the
case in which the rays are required to be pairwise disjoint. We derive a lower
bound on the number of color sequences that can be realized from any such fixed
point set and examine color sequences that can be realized regardless of the
point set, exhibiting negative examples as well. We also provide a tight upper
bound on the number of configurations that can be realized from a point set,
and point sets for which there are asymptotically less configurations than that
number. In addition, we provide algorithms to decide whether a color sequence
is realizable from a given point set in a line or in general position. We
address afterwards the variant of the problem where the rays are allowed to
intersect. We prove that for some configurations and point sets, the number of
ray crossings must be $\Theta(n^2)$ and study then configurations that can be
realized by rays that pairwise cross. We show that there are point sets for
which the number of configurations that can be realized by pairwisecrossing
rays is asymptotically smaller than the number of configurations realizable by
pairwisedisjoint rays. We provide also point sets from which any configuration
can be realized by pairwisecrossing rays and show that there is no
configuration that can be realized by pairwisecrossing rays from every point
set.

Motivated by the analysis of range queries in databases, we introduce the
computation of the Depth Distribution of a set $\mathcal{B}$ of axis aligned
boxes, whose computation generalizes that of the Klee's Measure and of the
Maximum Depth. In the worst case over instances of fixed input size $n$, we
describe an algorithm of complexity within $O({n^\frac{d+1}{2}\log n})$, using
space within $O({n\log n})$, mixing two techniques previously used to compute
the Klee's Measure. We refine this result and previous results on the Klee's
Measure and the Maximum Depth for various measures of difficulty of the input,
such as the profile of the input and the degeneracy of the intersection graph
formed by the boxes.

An edgeordered graph is a graph with a total ordering of its edges. A path
$P=v_1v_2\ldots v_k$ in an edgeordered graph is called increasing if
$(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k2$; it is called
decreasing if $(v_iv_{i+1}) < (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k2$. We
say that $P$ is monotone if it is increasing or decreasing. A rooted tree $T$
in an edgeordered graph is called monotone if either every path from the root
of to a leaf is increasing or every path from the root to a leaf is decreasing.
A geometric graph is a graph whose vertices are points in the plane and whose
edges are straight line segments. Let $G$ be a graph. Let
$\overline{\alpha}(G)$ be the maximum integer such that every edgeordered
geometric graph isomorphic to $G$ %under any edge labeling contains a monotone
noncrossing path of length $\overline{\alpha}(G)$. Let $\overline{\tau}(G)$ be
the maximum integer such that every edgeordered geometric graph isomorphic to
$G$ %under any edge labeling contains a monotone noncrossing complete binary
tree of size $\overline{\tau}(G)$. In this paper we show that $\overline
\alpha(K_n) = \Omega(\log\log n)$, $\overline \alpha(K_n) = O(\log n)$,
$\overline \tau(K_n) = \Omega(\log\log \log n)$ and $\overline \tau(K_n) =
O(\sqrt{n \log n})$.

Given a convex polygon of $n$ sides, one can draw $n$ disks (called side
disks) where each disk has a different side of the polygon as diameter and the
midpoint of the side as its center. The intersection graph of such disks is the
undirected graph with vertices the $n$ disks and two disks are adjacent if and
only if they have a point in common. We prove that for every convex polygon
this graph is planar. Particularly, for $n=5$, this shows that for any convex
pentagon there are two disks among the five side disks that do not intersect,
which means that $K_5$ is never the intersection graph of such five disks. For
$n=6$, we then have that for any convex hexagon the intersection graph of the
side disks does not contain $K_{3,3}$ as subgraph.

In 2001, K\'arolyi, Pach and T\'oth introduced a family of point sets to
solve an Erd\H{o}sSzekeres type problem; which have been used to solve several
other Ed\H{o}sSzekeres type problems. In this paper we refer to these sets as
nested almost convex sets. A nested almost convex set $\mathcal{X}$ has the
property that the interior of every triangle determined by three points in the
same convex layer of $\mathcal{X}$, contains exactly one point of
$\mathcal{X}$. In this paper, we introduce a characterization of nested almost
convex sets. Our characterization implies that there exists at most one (up to
order type) nested almost convex set of $n$ points. We use our characterization
to obtain a linear time algorithm to construct nested almost convex sets of $n$
points, with integer coordinates of absolute values at most $O(n^{\log_2 5})$.
Finally, we use our characterization to obtain an $O(n\log n)$time algorithm
to determine whether a set of points is a nested almost convex set.

Given two point sets $R$ and $B$ in the plane, with cardinalities $m$ and
$n$, respectively, and each set stored in a separate Rtree, we present an
algorithm to decide whether $R$ and $B$ are linearly separable. Our algorithm
exploits the structure of the Rtrees, loading into the main memory only
relevant data, and runs in $O(m\log m + n\log n)$ time in the worst case. As
experimental results, we implement the proposed algorithm and executed it on
several real and synthetic point sets, showing that the percentage of nodes of
the Rtrees that are accessed and the memory usage are low in these cases. We
also present an algorithm to compute the convex hull of $n$ planar points given
in an Rtree, running in $O(n\log n)$ time in the worst case.

The KLEE'S MESURE of $n$ axisparallel boxes in $\mathbb{R}^d$ is the volume
of their union. It can be computed in time within $O(n^{d/2})$ in the worst
case. We describe three techniques to boost its computation: one based on some
type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of
the structure of the input. The first technique benefits from instances where
the MAXIMA of the input is of small size $h$, and yields a solution running in
time within $O(n\log^{2d2}{h}+ h^{d/2}) \subseteq O(n^{d/2}$). The second
technique takes advantage of instances where no $d$dimensional axisaligned
hyperplane intersects more than $k$ boxes in some dimension, and yields a
solution running in time within $O(n \log n + n k^{(d2)/2}) \subseteq
O(n^{d/2})$. The third technique takes advantage of instances where the
\emph{intersection graph} of the input has small treewidth $\omega$. It yields
an algorithm running in time within $O(n^4\omega \log \omega + n (\omega \log
\omega)^{d/2})$ in general, and in time within $O(n \log n + n \omega ^{d/2})$
if an optimal tree decomposition of the intersection graph is given. We show
how to combine these techniques in an algorithm which takes advantage of all
three configurations.

Divideandconquer is a central paradigm for the design of algorithms,
through which some fundamental computational problems, such as sorting arrays
and computing convex hulls, are solved in optimal time within
$\Theta(n\log{n})$ in the worst case over instances of size $n$. A finer
analysis of those problems yields complexities within $O(n(1 + \mathcal{H}(n_1,
\dots, n_k))) \subseteq O(n(1{+}\log{k})) \subseteq O(n\log{n})$ in the worst
case over all instances of size $n$ composed of $k$ "easy" fragments of
respective sizes $n_1, \dots, n_k$ summing to $n$, where the entropy function
$\mathcal{H}(n_1, \dots, n_k) = \sum_{i=1}^k{\frac{n_i}{n}}\log{\frac{n}{n_i}}$
measures the "difficulty" of the instance. We consider whether such refined
analysis can be applied to other algorithms based on divideandconquer, such
as polynomial multiplication, inputorder adaptive computation of convex hulls
in 2D and 3D, and computation of Delaunay triangulations.

Given a set $P$ of $n$ points in the plane, we study the computation of the
probability distribution function of both the area and perimeter of the convex
hull of a random subset $S$ of $P$. The random subset $S$ is formed by drawing
each point $p$ of $P$ independently with a given rational probability $\pi_p$.
For both measures of the convex hull, we show that it is \#Phard to compute
the probability that the measure is at least a given bound $w$. For
$\varepsilon\in(0,1)$, we provide an algorithm that runs in
$O(n^{6}/\varepsilon)$ time and returns a value that is between the probability
that the area is at least $w$, and the probability that the area is at least
$(1\varepsilon)w$. For the perimeter, we show a similar algorithm running in
$O(n^{6}/\varepsilon)$ time. Finally, given $\varepsilon,\delta\in(0,1)$ and
for any measure, we show an $O(n\log n+ (n/\varepsilon^2)\log(1/\delta))$time
Monte Carlo algorithm that returns a value that, with probability of success at
least $1\delta$, differs at most $\varepsilon$ from the probability that the
measure is at least $w$.

The SwapInsert Correction distance from a string $S$ of length $n$ to
another string $L$ of length $m\geq n$ on the alphabet $[1..d]$ is the minimum
number of insertions, and swaps of pairs of adjacent symbols, converting $S$
into $L$. Contrarily to other correction distances, computing it is NPHard in
the size $d$ of the alphabet. We describe an algorithm computing this distance
in time within $O(d^2 nm g^{d1})$, where there are $n_\alpha$ occurrences of
$\alpha$ in $S$, $m_\alpha$ occurrences of $\alpha$ in $L$, and where
$g=\max_{\alpha\in[1..d]} \min\{n_\alpha,m_\alphan_\alpha\}$ measures the
difficulty of the instance. The difficulty $g$ is bounded by above by various
terms, such as the length of the shortest string $S$, and by the maximum number
of occurrences of a single character in $S$. Those results illustrate how, in
many cases, the correction distance between two strings can be easier to
compute than in the worst case scenario.

A set of intervals is independent when the intervals are pairwise disjoint.
In the interval selection problem we are given a set $\mathbb{I}$ of intervals
and we want to find an independent subset of intervals of largest cardinality.
Let $\alpha(\mathbb{I})$ denote the cardinality of an optimal solution. We
discuss the estimation of $\alpha(\mathbb{I})$ in the streaming model, where we
only have onetime, sequential access to the input intervals, the endpoints of
the intervals lie in $\{1,...,n \}$, and the amount of the memory is
constrained.
For intervals of different sizes, we provide an algorithm in the data stream
model that computes an estimate $\hat\alpha$ of $\alpha(\mathbb{I})$ that, with
probability at least $2/3$, satisfies $\tfrac 12(1\varepsilon)
\alpha(\mathbb{I}) \le \hat\alpha \le \alpha(\mathbb{I})$. For samelength
intervals, we provide another algorithm in the data stream model that computes
an estimate $\hat\alpha$ of $\alpha(\mathbb{I})$ that, with probability at
least $2/3$, satisfies $\tfrac 23(1\varepsilon) \alpha(\mathbb{I}) \le
\hat\alpha \le \alpha(\mathbb{I})$. The space used by our algorithms is bounded
by a polynomial in $\varepsilon^{1}$ and $\log n$. We also show that no better
estimations can be achieved using $o(n)$ bits of storage.
We also develop new, approximate solutions to the interval selection problem,
where we want to report a feasible solution, that use $O(\alpha(\mathbb{I}))$
space. Our algorithms for the interval selection problem match the optimal
results by Emek, Halld{\'o}rsson and Ros{\'e}n [SpaceConstrained Interval
Selection, ICALP 2012], but are much simpler.

We consider a natural variation of the concept of stabbing a segment by a
simple polygon: a segment is stabbed by a simple polygon $\mathcal{P}$ if at
least one of its two endpoints is contained in $\mathcal{P}$. A segment set $S$
is stabbed by $\mathcal{P}$ if every segment of $S$ is stabbed by
$\mathcal{P}$. We show that if $S$ is a set of pairwise disjoint segments, the
problem of computing the minimum perimeter polygon stabbing $S$ can be solved
in polynomial time. We also prove that for general segments the problem is
NPhard. Further, an adaptation of our polynomialtime algorithm solves an open
problem posed by L\"offler and van Kreveld [Algorithmica 56(2), 236269
(2010)] about finding a maximum perimeter convex hull for a set of imprecise
points modeled as line segments.

Finding a maximum independent set (MIS) of a given fam ily of axisparallel
rectangles is a basic problem in computational geom etry and combinatorics.
This problem has attracted significant atten tion since the sixties, when
Wegner conjectured that the corresponding duality gap, i.e., the maximum
possible ratio between the maximum independent set and the minimum hitting set
(MHS), is bounded by a universal constant. An interesting special case, that
may prove use ful to tackling the general problem, is the
diagonalintersecting case, in which the given family of rectangles is
intersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6
approximation algorithm for MHS in this setting, and showed that the duality
gap is between 3/2 and 6. In this paper we improve upon these results. First we
show that MIS in diagonalintersecting families is NPcomplete, providing one
smallest subclass for which MIS is provably hard. Then, we derive an
$O(n^2)$time algorithm for the maximum weight independent set when, in
addition the rectangles intersect below the diagonal. This improves and extends
a classic result of Lubiw, and amounts to obtain a 2approximation algo rithm
for the maximum weight independent set of rectangles intersecting a diagonal.
Finally, we prove that for diagonalintersecting families the duality gap is
between 2 and 4. The upper bound, which implies an approximation algorithm of
the same factor, follows from a simple com binatorial argument, while the
lower bound represents the best known lower bound on the duality gap, even in
the general case.

In 1926, Jarn\'ik introduced the problem of drawing a convex $n$gon with
vertices having integer coordinates. He constructed such a drawing in the grid
$[1,c\cdot n^{3/2}]^2$ for some constant $c>0$, and showed that this grid size
is optimal up to a constant factor. We consider the analogous problem for
drawing the double circle, and prove that it can be done within the same grid
size. Moreover, we give an O(n)time algorithm to construct such a point set.

We study a variation of the 1center problem in which, in addition to a
single supply facility, we are allowed to locate a highway. This highway
increases the transportation speed between any demand point and the facility.
That is, given a set $S$ of points and $v>1$, we are interested in locating the
facility point $f$ and the highway $h$ that minimize the expression $\max_{p\in
S}d_{h}(p,f)$, where $d_h$ is the time needed to travel between $p$ and $f$. We
consider two types of highways ({\em freeways} and {\em turnpikes}) and study
the cases in which the highway's length is fixed by the user (or can be
modified to further decrease the transportation time).

In this paper we study a facility location problem in the plane in which a
single point (facility) and a rapid transit line (highway) are simultaneously
located in order to minimize the total travel time from the clients to the
facility, using the $L_1$ or Manhattan metric. The rapid transit line is given
by a segment with any length and orientation, and is an alternative
transportation line that can be used by the clients to reduce their travel time
to the facility. We study the variant of the problem in which clients can enter
and exit the highway at any point. We provide an $O(n^3)$time algorithm that
solves this variant, where $n$ is the number of clients. We also present a
detailed characterization of the solutions, which depends on the speed given in
the highway.

Given a set $S$ of $n$ points in the plane, a \emph{radial ordering} of $S$
with respect to a point $p$ (not in $S$) is a clockwise circular ordering of
the elements in $S$ by angle around $p$. If $S$ is twocolored, a \emph{colored
radial ordering} is a radial ordering of $S$ in which only the colors of the
points are considered. In this paper, we obtain bounds on the number of
distinct noncolored and colored radial orderings of $S$. We assume a strong
general position on $S$, not three points are collinear and not three
lineseach passing through a pair of points in $S$intersect in a point of
$\R^2\setminus S$. In the colored case, $S$ is a set of $2n$ points partitioned
into $n$ red and $n$ blue points, and $n$ is even. We prove that: the number of
distinct radial orderings of $S$ is at most $O(n^4)$ and at least
$\Omega(n^3)$; the number of colored radial orderings of $S$ is at most
$O(n^4)$ and at least $\Omega(n)$; there exist sets of points with
$\Theta(n^4)$ colored radial orderings and sets of points with only $O(n^2)$
colored radial orderings.