\documentclass{article}
%\usepackage[nocapsections,noperiods,sfsections]{fixacm}
\usepackage{amsmath,latexsym,graphicx,subfigure,url,epsfig}

\sloppy

%\renewcommand{%\includegraphics}[1]{}
%\setlength{\parskip}{1.5em}

\newcommand{\comment}[1]{}

\newenvironment{proof}{\begin{trivlist}
 \item[] {\em Proof:}}{\null\hfill $\Box$
                       \end{trivlist}}

\newcommand{\parity}{\textsc{Colored-Parity}}
\newcommand{\dual}{\varphi}
\newcommand{\etal}{et al}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{open}{Open Problem}

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
%\newcommand{\bt}{\begin{tabbing}}
%\newcommand{\et}{\end{tabbing}}
%\newcommand{\be}{\begin{enumerate}}
%\newcommand{\ee}{\end{enumerate}}
%\newcommand{\bl}{\hspace*{2mm}}
%\newcommand{\Bl}{\hspace*{5mm}}
%\newcommand{\BL}{\hspace*{10mm}}
%\renewcommand{\email}{\affaddr}

% Macro to force a line break between authors in \author.
% Note that this definition has to come before \maketitle, not necc. \author.
\def\andlinebreak{\end{tabular}\linebreak\begin{tabular}[t]{c}}

% Generate hyperlinked DVI, PS, and PDF.
% Best used either with "latex" + "dvips -z", or with "pdflatex".
% If you generate PS or PDF via another mechanism, e.g., "dvipdf",
% you should add e.g. [dvipdf] to the \usepackage{hyperref} line.
% pdftitle is set automatically, but you can override and/or set pdfauthor.
\usepackage
  [breaklinks,bookmarks,bookmarksnumbered,bookmarksopen,bookmarksopenlevel=2]
  {hyperref}
{\makeatletter \hypersetup{pdftitle={\@title}}}
%\hypersetup{pdfauthor={}}


\begin{document}

\title{Separating point sets in polygonal environments}

%\conferenceinfo{SCG'04,} {June 8--11, 2004, Brooklyn, New York, USA.}

%\CopyrightYear{2004}

%\crdata{1-58113-885-7/04/0006} 

%\numberofauthors{8}

%\let\email\affaddr
\newcommand{\affaddr}{}
\newcommand{\email}{}
\author{
        Erik D. Demaine\thanks{
        MIT Computer Science and Artificial Intelligence Laboratory,
%      32 Vassar St., Cambridge, MA 02139, USA,
        {\tt edemaine@mit.edu}}
   \and Jeff Erickson\thanks{
        Dept. of Computer Science,
        Univ. of Illinois at Urbana-Champaign,
%        1304 W. Springfield Avenue,
%        Urbana, IL  61801, USA.
        {\tt jeffe@cs.uiuc.edu}}
   \and Ferran Hurtado\thanks{Departement de Matem\`atica Aplicada II, 
        Universitat Polit\`{e}cnica de Catalunya
%        Pau Gargallo 5,
%        08028 Barcelona, Spain.
        {\tt Ferran.Hurtado@upc.es}. Partially supported by  DURSI
      2001SGR00224, Acci\'o Integrada UPC-McGill (DURSI2004) and MCYT
      BFM2003-0368.}
   \and John Iacono\thanks{
        Dept. of Computer and Information Science,
        Polytechnic University,
%        5 MetroTech Center,
%        Brooklyn, NY, 11201, USA.
        {\tt jiacono@poly.edu}}
   \and Stefan Langerman\thanks{
        Chercheur qualifi\'e du FNRS,
	D\'epartement d'Informatique,
        Universit\'{e} Libre de Bruxelles, 
%        ULB CP212,
%        Av. F. D. Roosevelt 50,
%        1050 Bruxelles, Belgium.
        {\tt stefan.langerman@ulb.ac.be}}
   \and Henk Meijer\thanks{
        School of Computing,
        Queen's University,
%        Kingston, Ontario, K7L 3N6, Canada.
        {\tt henk@cs.queensu.ca}}
   \and Mark Overmars\thanks{
        Institute of Information and Computing Sciences,
        Utrecht University,
%        P.O.Box 80.089, 3508 TB Utrecht,
%        the Netherlands.
        {\tt markov@cs.uu.nl}}
   \and Sue Whitesides\thanks{
        School of Computer Science,
        McGill University,
%        3480 University St. room 318,
%        Montreal, Quebec H3A 2A7, Canada.
        {\tt sue@cs.mcgill.ca} Partially supported by grants from NSERC
	and FCAR.}
}

\iffalse
\author{
  \begin{tabular}{cc}
    Erik D. Demaine &
      Jeff Erickson\\
    \affaddr{MIT Laboratory}&
      \affaddr{Department of Computer Science}\\
    \affaddr{for Computer Science} &
      \affaddr{U. of Illinois at Urbana-Champaign}\\
%    \affaddr{Cambridge MA 02139, USA} &
%      \affaddr{1304 W. Springfield Avenue}\\
    \email{edemaine@mit.edu} &
%      \affaddr{Urbana, IL  61801, USA}\\
%    &
      \email{jeffe@cs.uiuc.edu}
  \bigskip\\
    Ferran Hurtado\thanks{Partially supported by  DURSI
      2001SGR00224, Acci\'o Integrada UPC-McGill (DURSI2004) and MCYT
      BFM2003-0368.} & 
      John Iacono\\
    \affaddr{Departement de Matem\`atica Aplicada II} &
      \affaddr{Dept. of Computer and Information Science}\\
    \affaddr{Universitat Polit\`{e}cnica de Catalunya} &
      \affaddr{Polytechnic University}\\
%      \affaddr{5 MetroTech Center}\\
%    \affaddr{Pau Gargallo 5} &
%      \affaddr{Brooklyn, NY, 11201, USA}\\
%    \affaddr{08028 Barcelona, Spain} &
    \email{Ferran.Hurtado@upc.es} &
      \email{jiacono@poly.edu} \\
  \bigskip\\
    Stefan Langerman\thanks{Charg\'{e} de recherches du FNRS.} &
      Henk Meijer\\
      \affaddr{D\'epartement d'Informatique} &
    \affaddr{School of Computing}\\
    \affaddr{Universit\'{e} Libre de Bruxelles} &
 %   \affaddr{ULB CP212, Av. F. D. Roosevelt 50} &
      \affaddr{Queen's University}\\
%    \affaddr{1050 Bruxelles, Belgium} &
%      \affaddr{Kingston, ON, K7L 3N6, Canada}\\
    \email{Stefan.Langerman@ulb.ac.be} &
      \email{henk@cs.queensu.ca}
  \bigskip\\
    Mark Overmars &
      Sue Whitesides\\
    \affaddr{Institute of Information and Computing Sciences} &
      \affaddr{School of Computer Science}\\
    \affaddr{Utrecht University} &
      \affaddr{McGill University}\\
 %   \affaddr{P.O.Box 80.089} &
 %     \affaddr{3480 University St. room 318}\\
 %   \affaddr{3508 TB Utrecht, the Netherlands} &
 %     \affaddr{Montreal, Quebec H3A 2A7, Canada}\\
    \email{markov@cs.uu.nl} &
      \email{sue@cs.mcgill.ca}
  \end{tabular}
}
\fi

\maketitle


% Set the default figure placement to [!htbp].  Relies on LaTeX internals.
{\makeatletter \gdef\fps@figure{htb}}


%\def\scale{0.75}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}
  We consider the separability of two point sets inside a polygon by
means of chords or geodesic lines. Specifically, given a set of
red points and a set of blue points in the interior of a polygon,
we provide necessary and sufficient conditions for the existence
of a chord and for the existence of a geodesic path that separate
the two sets; when they exist we also derive efficient algorithms
for their obtention. We also study the separation of the two
sets using the minimum number of pairwise non-crossing chords.
\end{abstract}

%\category{F.2.2}{Nonnumerical Algorithms and Problems}{}
%\keywords{polygons, chords, geodesics, separability}
%\terms{Algorithms}

%\vfill\eject
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}\label{section:introduction}

Given two point sets $R$ and $B$ in the interior of a polygon
(the \emph{red points} and the \emph{blue points}, respectively),
is there a chord separating $R$ from $B$?
This basic question is the starting point for our paper,
and one of several related problems we study.

Problems on separability of point sets and other geometric objects
have generated a significant body of research in computational
geometry.  Many kinds of separators have been considered, including
lines \cite{megiddo}, circles \cite{B88,BCDUY96}, convex
polygons \cite{EP88}, and wedges and strips \cite{HNRS98}.
A thorough study is given in \cite{thesis}. The main motivations
underlying these different works arise in disciplines such as
spatial data organization, statistical analysis, and more generally,
wherever methods for clustering or classification are useful.

In the plane, an ideal paradigm of separability is by means
of a single line, whenever possible.
(The analog in higher dimensions is a hyperplane, but we focus here
on two dimensions.)
A line partitions the plane into two clean regions,
and gives an easy classification rule for any query point
(the sidedness test).
However, if we constrain our working space to the interior of a polygon,
an otherwise linearly separable population of points may lie in many different
cells (Figure~\ref{lineversuschord}, left).
On the other hand, the two point sets may be separable by just one chord
of the polygon, while no linear separation exists
in the underlying plane without the polygon boundaries
(Figure~\ref{lineversuschord}, right).

\begin{figure}
%  \centerline{\includegraphics[scale=\scale]{lineversuschord-bs.eps}}
  \centerline{\includegraphics[width=.9\linewidth]{lineversuschord-bs.eps}}
  \caption{Left:~red and blue points that are linearly separable in the plane
           but generate many regions in the polygon.  Right:~a chord that
           separates point sets which cannot be separated with a
           line in the plane.}
  \label{lineversuschord}
\end{figure}

The study of basic geometric structures in the interior of a polygon
naturally leads to the study of geodesics (shortest paths) in the polygon.
This topic has also attracted a lot of attention.
Some examples are the geodesic diameter \cite{suri},
the relative convex hull \cite{godfried1},
the 1-center problem \cite{PSR89,asano},
the geodesic Voronoi diagrams \cite{aronov1,aronov2,dtlee},
and most recently,
geodesic ham-sandwich separators \cite{ham-sandwich}.


In Section~\ref{section:linear} we study, both from the structural
and computational viewpoint, the two more natural ways to separate
point sets in a polygon: by means of one chord, and by means of a
single geodesic line, i.e., a shortest path between two boundary
points. In fact, we prove that the necessary and sufficient
conditions for both kinds of separability are closely related.
In both cases we obtain polynomial-time algorithms to find
a separator or report that none exists.

In Section~\ref{section:manychords} we study the problem of
separating the two point sets using as few non-crossing chords as
possible.
We show that the problem is polynomially solvable when
the polygon is combinatorially very simple, and that the problem becomes
NP-complete when the polygon may have holes.
In between, there remains an intriguing open problem.


Throughout this paper, $R$ (the \emph{red points})
and $B$ (the \emph{blue points}) are two given finite sets of points
inside a given polygon~$P$.
Their cardinalities are denoted by $r=|R|$ and $b=|B|$. 
%The points in $R\cup B$ are occasionally called
%\emph{sites}. 
The total number points in $R\cup B$, plus the number of vertices
of the polygon~$P$, is denoted by~$n$.
We let $k$ denote the number of reflex vertices of the polygon~$P$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Linear separability}\label{section:linear}

Let $C$ be a simple curve connecting two points on the boundary of a
polygon $P$. $C$ decomposes $P$ into two closed subsets
$\overline{C}^+$ and $\overline{C}^-$, with
$\overline{C}^+\cup\overline{C}^- = P$ and $\overline{C}^+ \cap
\overline{C}^- = C$. We also write $C^+=\overline{C}^+ - C$ and
$C^-=\overline{C}^- - C$. We say that $C$ \emph{separates} two sets
$R$ and $B$ if $R\subseteq C^\alpha$ and $B\subseteq C^\beta$,
where $\alpha=+,\beta=-$ or $\alpha=-,\beta=+$. We say that $C$
\emph{weakly separates} two sets $R$ and $B$ if $R\subseteq
\overline{C}^\alpha$ and $B\subseteq \overline{C}^\beta$.

When the curve $C$ is a geodesic, the sets $\overline{C}^+$ and 
$\overline{C}^-$ are called \emph{half-polygons}. 
The \emph{geodesic convex hull} $GH(S)$ 
(also called the \emph{relative convex hull})
for a set $S$ of points inside a polygon $P$ is the intersection of
all half-polygons that contain $S$.

\begin{theorem}\label{thm:chord-sep}
Two sets of points in a polygon $P$ are separable by a
chord if and only if their geodesic convex hulls are disjoint.
\end{theorem}

\begin{proof}
Let $C$ be a chord with endpoints $p$ and $q$ separating sets $R$
and $B$ in $P$. A chord is a geodesic line, so by the definition
of geodesic convex hulls, $GH(R)\subseteq \overline{C}^\alpha$ and 
$GH(B)\subseteq \overline{C}^\beta$, and so,
$GH(R)\cap GH(B) \subseteq C$. Moreover,
since $C$ does not contain any points of $R$ or $B$, $GH(R)$
(resp. $GH(B)$) cannot contain $p$ or $q$ unless that point is a
reflex vertex in $C^\alpha$ (resp. $C^\beta$), and $GH(R)$ (resp.
$GH(B)$) cannot contain an interior point of $C$ unless it
contains both $p$ and $q$. Note that $p$ can only be a reflex
vertex for at most one of $C^\alpha$ and $C^\beta$. This implies
that $GH(R)$ and $GH(B)$ cannot intersect.

Now suppose $GH(R)$ and $GH(B)$ are disjoint.
%% new false proof
\iffalse
Let $G$ be the geodesic between some point of $R$ and some point 
of $B$. 
We define the \emph{separating subpolygon} Q as the component
of $P-GH(R)-GH(B)$ whose interior intersects $G$.
Note that there can only be one such component

Both geodesic convex hulls are composed of a sequence of convex chains
separated by at most $k$ reflex vertices from polygon $P$. We color
those reflex vertices of $P$ according to the color of the geodesic
convex hull they belong to.
Note that while walking on the boundary of $P$ in clockwise order,
we do not encounter a color alternation red,blue,red,blue. Otherwise,
the geodesic connecting the two red vertices would intersect the
geodesic connecting the two blue vertices, which would imply that
$GH(R)$ and $GH(B)$ are not be disjoint.
Consider the consecutive red-blue colored reflex vertices in clockwise
order around $P$, $p_r,p_b$ and $q_b,q_r$, and define the
\emph{separating subpolygon} $Q$ formed by walking $P$ in clockwise
order from $p_r$ to $p_b$, then $GH(B)$ in counterclockwise order
along the convex chain from $p_b$ to $q_b$, then $P$ in clockwise
order from $q_b$ to $q_r$ and finally $GH(R)$ in counterclockwise
order along the convex chain from $q_r$ to $p_r$. The removal of $Q$
from $P$ separates $P$ into two regions, one of which contains all the
points in $B$ and the other containing all the points in $R$.
This implies that any geodesic $G$ from a red point to a blue point will
intersect $Q$. Furthermore, $G$ will intersect the convex chains from
$p_b$ to $q_b$ and from $q_r$ to $p_r$.

Let $L$ be a line separating the two convex chains from
$p_b$ to $q_b$ and from $q_r$ to $p_r$, and which is not incident to
any vertices in $P$.
By the Jordan curve theorem, $L$ intersects $G$.
Let $c$ be a component  of $L \cap Q$ that intersects $G$.
Since $G$ is a geodesic, the chord $c$ has one endpoint between
$p_r$ and $p_b$ and the other between $q_b$ and $q_r$, and so
$c$ separates $R$ and $B$.
\fi
%% SL: Old proof.
Let $D$
be the shortest geodesic with endpoints $u\in GH(R)$ and
$v\in GH(B)$, let $s$ be some line segment from $D$,
let $\ell$ be the bisector of $s$, and let $m=s\cap\ell$.
Define the chord $C=(p,q)$ where $p$ and $q$ are the
intersections of $\ell$ and the boundary of $P$ closest to
$m$ in both directions.
%% as the component of $P\cap\ell$ that intersects $s$.
We claim that the chord $C$ separates $GH(R)$ and $GH(B)$.
Suppose that on the contrary, the boundary of $GH(R)$
intersects the segment $mp$, and let $p'$ be the intersection
closest to $m$. Let $Q$ be the Jordan curve composed
of the portion of $D$ from $m$ to $u$, the boundary of
$GH(R)$ from $u$ to $p'$, and the segment from $p'$ to $m$.
Note that the boundary of $P$ does not intersect the interior
of the region surrounded by $Q$, and so the geodesics from
$m$ to $u$ and from $u$ to $p'$ (which only intersect in $u$)
are both concave.
% SL: I don't know why I did this...
%Let $u'$ be the intersection of the support line of $s$ and
%the geodesic from $u$ to $p'$, and
Consider the ray $r$ from $m$, orthogonal to the line
$up'$, and intersecting that line in $u'$, and let $u''$
be the first intersection of $r$ and the geodesic from $u$
to $p'$.
Since the geodesic from $u$ to $p'$ is concave, the geodesic
distance from $m$ to $u$ is
$d(m,u)\geq d(m,u') > d(m,u'')$, and
$d(v,u)=d(v,m)+d(m,u)>d(v,m)+d(m,u'')>d(v,u'')$.
This implies that $D$ was not the shortest geodesic from $R$
to $B$, a contradiction.
\end{proof}

\begin{lemma}
If $GH(R)$ and $GH(B)$ do not intersect,
the two points $u\in GH(R)$ and $v\in GH(B)$
that minimize the length of the geodesic path between $u$ and 
$v$ can be found in $O(n)$ time.
\end{lemma}
\begin{proof}
Consider a point $v\in GH(B)$, and a point $u\in GH(R)$. If the geodesic
path from $v$ to $u$ (excluding $u$) intersects $GH(R)$ then $u$
cannot be the closest point from $v$ in $GH(R)$. The same is
true for $GH(B)$ and $v$.
Let $\hat{d}(v,u)$ be the length of that geodesic path if it does not
intersect $GH(R)$ and $GH(B)$ and $\infty$ otherwise. 
Note that the set of points $u$ on the boundary of $GH(R)$ for which 
$\hat{d}(v,u)<\infty$ forms a convex chain. 
It can be shown that the arc-length parameterization of the geodesic 
distance from a fixed point $u$ to a point $v$ on that convex chain is
a convex function. This implies 
the matrix $\hat{d}(v,u)$ for all vertices $v$ of
$GH(B)$ and $u$ of $GH(R)$ has every row and every column
unimodal and a local minimum is a global minimum. 
So we can find the minimum in the array after 
querying $O(\log^2{n})$ entries using a two-dimensional 
Fibonacci search.
Querying $\hat{d}(v,u)$ can be done in $O(\log{n})$ time after $O(n)$
time preprocessing using the data structure of Guibas and Hershberger
\cite{gh-ospqs-89}.
Once the minimum found, we can report the shortest path between the
two remaining edges in linear time using the same data structure.
\end{proof}

\begin{corollary}\label{cor:chord-sep}
There is an $O(n\log{n})$ algorithm that, given sets $R$ of red
points and $B$ of blue points in a simple polygon $P$, either finds
a chord that separates $R$ and $B$ or reports that no such
chord exists.
\end{corollary}
\begin{proof}
Computing $GH(R)$ and $GH(B)$ can be done in $O(n\log{n})$ time \cite{godfried1}
and verifying that they don't intersect can be done within the
same time bound. 
By the previous lemma, we can find the shortest geodesic connecting 
$GH(A)$ and $GH(B)$ in $O(n)$ time. The separating chord 
can then be found in $O(n)$ time.
\end{proof}

\begin{theorem}\label{thm:geod-sep}
Two sets of points in a polygon $P$ are weakly separable by a
geodesic line
if and only if the interiors of their geodesic convex hulls are disjoint.
\end{theorem}

\begin{proof}
By the definition of a geodesic convex hull, if a geodesic line
$C$ weakly separates $R$ and $B$ in $P$, then
$GH(R)\subseteq\overline{C}^\alpha$ and
$GH(B)\subseteq\overline{C}^\beta$, and so $GH(R)$ and $GH(B)$
have disjoint interiors.

On the other hand, if $GH(R)$ and $GH(B)$ have disjoint interiors,
then
%This implies that the curve
$I=GH(R)\cap GH(B)$, if not empty, is a curve. Furthermore, it is a
geodesic between its two endpoints $u$ and $v$. The
boundaries of $GH(R)$ and $GH(B)$ are intersecting on one side of
$u$, and start with two disjoint line segments $s_\alpha$ and
$s_\beta$ on the other side. Draw a line segment from $u$ along a
ray bisecting the angle between $s_\alpha$ and $s_\beta$, until
the first intersection with $P$, and do the same for $v$. The
resulting curve $I'$ is a geodesic line because it is the
concatenation of three geodesics: $I$ and two line segments, and is
locally optimal at both endpoints of $I$.
We further claim it weakly
separates $R$ and $B$. Indeed, suppose that the ray from $u$ is
intersected by $GH(R)$, and let $u'$ be the closest intersection
to $u$. The segment $uu'$ is not intersected by the boundary of
$P$, so that segment must be contained in $GH(R)$, but then $uu'$
must also be included in $GH(B)$ since $uu'$ bisects the angle
between $s_\alpha$ and $s_\beta$, and therefore $uu' \subseteq I$,
which is a contradiction.
\end{proof}

\begin{corollary}
There is an $O(n\log{n})$ algorithm that, given sets $R$ of red
points and $B$ of blue points in a simple polygon $P$, either finds
a geodesic that weakly separates $R$ and $B$ or reports that no such
geodesic exists.
\end{corollary}
\begin{proof}
Computing $GH(R)$ and $GH(B)$ can be done in $O(n\log{n})$ time, 
and verifying that their interiors don't intersect can be done
within the same time bound using a line sweep algorithm.
If there is a separating chord, we can find it in $O(n\log{n})$ time
using the algorithm from Corollary~\ref{cor:chord-sep}.
Otherwise, find $I=GH(R)\cap GH(B)$ in $O(n\log{n})$ time using a
line sweep algorithm, and extend $I$ as explained in
Theorem~\ref{thm:geod-sep}.
\end{proof}

\begin{theorem}\label{thm:chordsep-lb}
Given sets $R$ of red points and $B$ of blue points in a simple
polygon $P$, deciding whether any geodesic (or any chord) in $P$
separates $r$ from $B$ requires $\Omega(n\log n)$ time in the
algebraic computation tree model.
\end{theorem}
\begin{proof}
We prove the lower bound by describing a linear-time reduction from the integer set
intersection problem: Given two sets $X$ and $Y$ of integers,
determine whether any integer lies in both sets.\footnote{We can avoid
the restriction to integer sets by replacing the small fractions in our
construction with formal infinitesimals; however, this change would limit
our lower bound to algebraic \emph{decision} trees.}  Yao \cite{yao}
proved that solving this problem requires $\Omega(n\log n)$ time in the algebraic
computation tree model; the lower bound applies even if one
of the sets is given in sorted order.
Let $X$ be a set of $n$ integers, and let $Y$ be a sorted sequence
of $n$ integers.  We construct a simple polygon $P$ with $O(n)$ edges
as follows.  The polygon is a rectangle centered along the $x$-axis,
with a thin crack of width $1/8$, mostly along the $x$-axis.  For every
integer $y\in Y$, the crack has a square bump of width $1/2$ and height
$1$ centered at the point $(y, 1/2)$.  Next, we transform $Y$ into a set
of $n$ blue points $\{(y, 1/3) \mid y\in Y\}$.  Finally, we transform $X$
into a set of $n+4$ red points; a point at $(x, 2/3)$ for each $x\in X$,
plus two additional red points near the bottom corners of the large
rectangle.  The reduction can be performed in linear time in
the algebraic computation tree model.
If $X$ and $Y$ are disjoint, then all the non-corner red points are above
the crack.  In this case, the red and blue points can be separated by a
geodesic.  In fact, by making a few small adjustments to the ends of the
crack, we can guarantee that there actually is a separating chord; see
Figure~\ref{teeth}.
\begin{figure}
\centerline{\includegraphics[width=\linewidth]{teeth}}
\caption{The result of our reduction from $X = \{3,4,7,9,14,16\}$
         and $Y = \langle 1,5,8,12,15\rangle$.}
\label{teeth}
\end{figure}

On the other hand, if $X$ and $Y$ are not disjoint, then one of
the bumps in the crack has both a red point $r$ and a blue point
$b$ immediately below it.  Any geodesic that separates these two
points must pass below $r$ and above $b$; however, every separating
geodesic is above both of the bottom corner red points.  It follows
that the red and blue points cannot be separated by any geodesic in $P$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Separability by non-crossing chords}\label{section:manychords}

We consider next a natural generalization of one of the problems
studied in Section~\ref{section:linear}: to separate the two point
sets using as few non-crossing chords as possible.  If crossings
were allowed and the points were placed closely together, the
solution would consist of a minimum set of \emph{lines} separating
the sets in the plane, and finding such a set is known to be
NP-hard \cite{freimer}.

More precisely, we say that a set of chords \emph{weakly separates}
$R$ and $B$ if the open regions of the polygon bounded by the chords
each contain only points from at most one of $R$ or $B$, but not both. A set
of chords \emph{strictly separates} $R$ and $B$ if the closed regions
of the polygons bounded by the chords contain only points from $R$ or
$B$ but not both.
We show that the problem is polynomially solvable when $P$ is very
simple, namely a pair of parallel lines or a triangle, and becomes
NP-complete when $P$ may have holes.  In between, there is an
intriguing open problem on which we comment at the end of the paper.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Separating points inside a strip}

Let $R$ and $B$ be sets of red
and blue points in a vertical strip. 
We assume all points are not collinear on a vertical line.
This case is easily solved, e.g. in the strict separation case by
adding a horizontal chord at every color alternation. 
Theorem \ref{thm:chord-sep}
implies that if $R$ and $B$ are separable by a chord, then they
have disjoint convex hulls. In this case, $R$ and $B$ can be
weakly separated by a chord that passes through one red point and
one blue point, and this canonical separating chord can be found
in $O(n)$ time using linear programming \cite{megiddo}. 
In the more general case
where more than one chord is required to separate the red and blue
points, we define a canonical set of separating chords as follows.
Say that a chord is \emph{pinned} if it passes through a point in
$R\cup B$ and \emph{trapped} if it passes through two points in 
$R\cup B$.
A \emph{fan} is a set of chords with a common
endpoint, called its \emph{apex}.
% SL: Henk suggestion: define canonical fan
A \emph{canonical fan} is a fan where every chord is pinned and
at least one chord is trapped.
Finally, a set of chords that
weakly separate $R\cup B$ is \emph{canonical} if it consists of a
sequence of canonical fans whose apexes lie on alternate sides of
the strip.
% , where every chord is pinned and at least one chord in
% every fan is trapped.
See Figure \ref{strip}.
\begin{figure}
  \centerline{\includegraphics[width=.6\linewidth]{strip}}
  \caption{Left:~red and blue points in a strip, separated by
           non-crossing chords.  Right:~a canonical weak separation
           into the same red and blue subsets; thicker chords are
           trapped.}
  \label{strip}
\end{figure}

\begin{lemma}
\label{L:strip-canon}
Let $R$ and $B$ be sets of red and blue points in a strip.  For any
set of non-crossing chords that weakly separate $R$ and $B$, there is
a canonical set of non-crossing chords that weakly separate $R$ and
$B$ into the same subsets.
\end{lemma}
\begin{proof}
We describe an algorithm to make canonical any weakly-separating set $C$
of non-crossing chords.  The algorithm proceeds in two phases.  In the
first phase, we move each chord
% SL: Precising the order (cf Henk's comment)
in turn, from lowest to highest. Each chord is translated 
%
 downward as far as possible until it
touches either a point in $R\cup B$ or an endpoint of the next lower
chord.  In the latter case, we rotate the chord around the common
endpoint until it touches a point in $R\cup B$.  At the end of this
phase, every chord is pinned; we call the point in $R\cup B$ on any
chord the \emph{pivot}.
In the second phase, the algorithm maintains an \emph{active fan} of
chords with a common endpoint on one side of the strip.  The chords
below the active fan (if any) belong to an alternating sequence of
canonical fans; the apex of the active fan (if any) lies on the
opposite side of the strip from the highest canonical fan.  Initially,
the active fan consists of just the lowest chord; we can choose either
endpoint as the apex.  We lift the apex of the active fan, maintaining
contact between each chord in the fan and its pivot point, until one
of the following events occurs:
\begin{enumerate}
\item
The top chord in the active fan touches an endpoint of the next higher
chord.  In this case, we add the next higher chord to the active fan
and continue.
\item
The bottom chord in the active fan touches the apex of the next lower
canonical fan.  In this case, we \emph{freeze} the lowest chord,
removing it from the active fan and adding it to the next lower fan.
If the active fan is now empty, we use the next higher chord as the
new active fan.
\item
A chord in the active fan touches a second point in $R\cup B$.
(This includes the case where two
chords in the fan coincide.)  In this case, that chord is now trapped.
We freeze the active fan, and the next higher chord (if any) becomes
the new active fan, with its apex on the opposite side of the strip
from the old active fan's apex.
\end{enumerate}
The process ends when the topmost chord is frozen, at which point the
entire set of chords is canonical.
\end{proof}

\begin{theorem}\label{thm:strip}
A minimal set of non-crossing chords that weakly separate a set of red
points from a set of blue points in an infinite strip can be computed in
$O(n^5)$ time.
\end{theorem}
\begin{proof}
The previous lemma implies that it is sufficient to search for a minimal
\emph{canonical} set of non-crossing chords.  We compute such a set by
considering all possible sequences of non-crossing \emph{trapped} chords,
using a straightforward dynamic programming algorithm.  As we show below,
for each such sequence, the minimum number of additional non-trapped chords
that must be added to weakly separate the red and blue points can be
computed in linear time, after a global preprocessing stage.
For any two non-crossing trapped chords $t^-$ and $t^+$, where $t^-$ is
below $t^+$, let $T(t^-, t^+, \textsf{left})$ denote the minimum number
of non-crossing chords that weakly separate the red and blue points
between $t^-$ and $t^+$, where every chord shares either the
\textsf{left} endpoint of $t^-$ or the non-\textsf{left} endpoint
of $t^+$.
%; (2)~any points between $t^-$ and the next higher chord are of the
%same color as the \textsf{left} point on $t^-$; and (3)~any points
%between $t^+$ and the next lower chord are of the same color as the
%\textsf{left} point on $t^+$.
We define $T(t^-, t^+, \textsf{right})$ analogously.  See Figure~\ref{trapslash}.
\begin{figure}
  \centerline{\includegraphics[width=.6\linewidth]{trapslash}}
  \caption{$T(t^-, t^+, \textsf{left}) = 6$ and
            $T(t^-, t^+, \textsf{right}) = 8$.}
  \label{trapslash}
\end{figure}

We can easily compute $T(t^-, t^+, \textsf{left})$ by drawing a chord
through every point in the trapezoid, either from the bottom \textsf{left}
corner or from the top non-\textsf{left} corner---only one of these two
chords lies entirely within the strip---and then discarding any chord
that passes through a point of the same color as the chord above it.
%, or the \textsl{left} point of the top chord.  
With no preprocessing, this
computation requires $O(n\log n)$ time to sort points angularly around
the opposite corners of the trapezoid, plus $O(n)$ time to scan through
the sorted list.  We can speed this up by computing the arrangement of
lines dual to $R\cup B$ in an $O(n^2)$-time preprocessing phase.  The
angular order of $R\cup B$ around any point $p$ is identical to the order
in which the lines dual to $R\cup B$ intersect the line $p^*$ dual to $p$;
the Zone Theorem implies that we can compute this order in $O(n)$ time by
simply walking around the boundary of the zone of $p^*$.  A similar
algorithm computes $T(t^-, t^+, \textsf{right})$ in linear time.

Now for any trapped chord $t$, let $C(t, \textsf{left})$ denote the size
of the minimum canonical set of chords that weakly separate the red and
blue points on or above~$t$, where the apex of the lowest fan is the
\textsf{left} endpoint of $t$.
%, and the points between $t$ and the next
%higher chord have the same color as the \textsf{left} point on $t$.
We define $C(t, \textsf{right})$ analogously.  Clearly, $C(t,
\textsf{left}) = 0$ if all the points above $t$ have the same color
% as the \textsf{left} point on $t$
(in particular, if there are no points above $t$).  Otherwise, we have
the recurrence
\[
    C(t, \textsf{left}) = 1 +
    \min_{t'} \big(T(t, t', \textsf{left}) + C(t', \textsf{right}) \big)
\]
where $t'$ ranges over all trapped chords that lie entirely above
$t$. For each trapped chord $t$, the function $C(t,
\textsf{left})$ depends on $O(n^2)$ other trapped chords $t'$, and
each $T(t, t', \textsf{left})$ can be evaluated in time $O(n)$.
Thus, not counting recursion, we can compute $C(t, \textsf{left})$
in $O(n^3)$ time.  Since there are $O(n^2)$ trapped chords~$t$, we
can compute $C(t, \textsf{left})$---and analogously, $C(t,
\textsf{right})$---for \emph{all} $t$ in $O(n^5)$ time by
straightforward dynamic programming. Finally, the minimum number
of non-crossing chords that separate $R$ from $B$ is the smaller
of $C(-\infty, \textsf{left})$ and $C(-\infty, \textsf{right})$,
where $-\infty$ denotes a symbolic chord infinitely far below all
of the points.
\end{proof}

%
%  Modified by jeffe 02 Mar 2005
%
Our algorithm requires only slight modifications if we desire a minimal set
of chords that \emph{strictly} separate the red and blue points, where
no point in $R\cup B$ lies on a chord.  Instead of using the points
themselves to define canonical chord sets, we replace each point $p$
with two perturbed points $p^\flat = p - (0,\varepsilon)$ and $p^\sharp
= p + (0,\varepsilon)$, where $\varepsilon$ is a symbolic infinitesimal.
Now a pinned chord passes through at least one perturbed point $p^\sharp$
and a trapped chord passes through two perturbed points $p^\flat$ and
$q^\sharp$. The algorithm ignores all chords going through the
original points.  The remainder of the algorithm is unchanged.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Separating points in a triangle}
Now suppose the points lie inside a triangle.  If the optimal set of
separating chords has a simple linear structure, then a straightforward
generalization of our strip algorithm can find it in $O(n^5)$ time---we
simply treat two edges of the triangle as one side of the ``strip", with
the third edge forming the other side.  However, the optimal separating set
could have a tree-like structure instead, with a single central region
bounded by three chords and three (possibly empty) subsets of triangle
edges.  In this case, more effort is required, in part because we cannot
assume that any of these three chords passes through two points.
Figure \ref{triangle} shows a set of red and blue points separated by three
non-crossing chords; if we require some chord to pass through two
points, then at least four chords are required.
\begin{figure}
    \centerline{\includegraphics[width=.6\linewidth]{triangle}}
    \caption{Separating points in a triangle.  There is no separating
    set of three chords where one chord hits points of both colors.}
    \label{triangle}
\end{figure}
To find an optimal solution of this form, we must modify our definition
of ``canonical" separating sets.  We still require that the chords
comprise three sequences of alternating fans, where each fan contains
either a trapped chord or a bounding chord of the central region.  The central
region is bounded by three chords, which can be either trapped or merely
pinned.  However, any pinned chord must share an endpoint with an adjacent
chord, and two pinned chords can only share an endpoint if all three
central chords are pinned and form a triangle, as in Figure \ref{triangle}.
\begin{theorem}\label{thm:triangle}
A minimal set of non-crossing chords that weakly separate a set of red
points from a set of blue points in a triangle can be computed in
$O(n^6)$ time.
\end{theorem}
\begin{proof}
The algorithm begins by computing the optimal strip-like solution in
$O(n^5)$ time, and only then considers tree-like solutions.
There are $O(n^3)$ pinned triangles.  We can compute the optimal
decomposition outside any pinned triangle in $O(n^3)$ time, by determining
the trapped chord closest to each pinned triangle edge; the best
decomposition beyond that trapped chord was already computed during the
strip-like phase of the algorithm.
To handle the case where the central region has a trapped bounding chord,
we introduce a pair of \emph{ghost} chords.  These ghost chords form a
triangle with the trapped chord, and exactly one of the ghost chords passes
through an input point.  There are $O(n^3)$ ghost chords, and we can
compute the optimal decomposition outside each ghost chord in $O(n^3)$ time,
exactly as we did for trapped triangle edges.  (The ghost chords do not
actually contribute to the cost of the solution.)  Finally, for any trapped
chord, we can find the best pair of ghost chords in $O(n)$ time.
\end{proof}
For any constant $t$, a similar dynamic programming algorithm can
be used to separate red and blue points in any simple $t$-gon, or
any polygon with holes with a total of $t$ edges, in time
$n^{O(t)}$.  As $t$ increases, the algorithm considers chords
determined by larger subsets of input points. Since the algorithm
is inefficient even for very small values of $t$, we omit further
details. 
%\xxx[Jeff]{I'm punting; sue me.  If the optimal solution
%has several regions bounded by more than two chords, those chords
%could interfere with each other when we try to make the solution
%canonical, like the pinned triangle above. Even if every region is
%bounded by at most three chords, we can still get long
%interference chains; the running time depends on the maximum
%length of such a chain.  $O(n^{3t})$ is fairly easy.  I think I
%can show that (wlog) the longest such chain has at most $t+1$
%chords, by starting the canonicalization process near the
%``center" of the dual tree and working out to the leaves, adding
%half the chords in each large region to the chain.  That would
%give us a running time of $O(n^{t+4})$, but I don't think it's
%worth the effort to make sure.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Polygons with holes}
\begin{theorem}\label{thm:NP-hard}
Finding the minimal number of non-intersecting chords that separate blue
from red points in a polygon with holes is NP-hard.
\end{theorem}

\begin{proof}
Let $Exp(x)$ be a boolean expression in conjunctive normal form with $n$
variables and $m$ clauses such that each clause has three literals.  Let
$G_{Exp}$ be the graph $(V,E)$, where $V$ consists of the variables and
clauses of $Exp(x)$, and $(x_i,c_j) \in E$ if and only if variable $x_i$
occurs in clause $c_j$.  If $G_{Exp}$ is planar, then deciding whether
there is a assignment of true and false values for $x$ such that $Exp(x)$
is true is known as the \emph{planar 3SAT problem}.  If we also require
that each clause has exactly one true literal, the problem is known as
\emph{planar 1-in-3SAT}.  Laroche~\cite{laroche} proved that planar
1-in-3SAT is NP-complete.  We prove our theorem by describing a
polynomial-time reduction from this problem.

We first show how to create a polygon $P$ and a set of blue and red points
from a planar embedding of the graph $G_{Exp}$.  Figure \ref{fi:var.0} shows
the encoding of a variable.  
\begin{figure}[h]
   \begin{center}
   \input{variable.0.pstex_t}
   \end{center}
   \caption{A variable contained in six clauses; black and white dots
   represent blue and red points respectively.}
   \label{fi:var.0}
\end{figure}
We imagine that the boundary of the variable
gadget is oriented clockwise.  The \emph{inside} of the variable is the
connected portion of the boundary that bounds a hole; the remainder of the
boundary is the \emph{outside}.  There are exactly two minimal sets of
chords that separate the blue and red points within each variable gadget;
these correspond to assigning the values true and false to the variable.
The true setting consists of chords that from the inside of the variable
gadget go in clockwise direction across to the outside; in the false
setting, the chords are oriented counterclockwise.  Figure \ref{fi:var.2}
shows two close-ups of part of a variable, one set to true and one set
to false.  We assume that the true and false settings each consist of $k$
chords.  Notice that any other set of chords that separate the red and
blue points in a variable gadget requires more than $k$ chords.

\begin{figure}[ht]
   \begin{center}
   \input{variable.2.pstex_t}
   \end{center}
   \caption{True and false settings of a variable.}
   \label{fi:var.2}
\end{figure}

Clauses are encoded as equilateral triangles that meet their three variables
in the corners as shown in Figure \ref{fi:clause.0}.
A bump is placed on each side of a triangle to prevent chords from 
intersecting more than one variable gadget.
A variable gadget
meets a clause gadget on its outside boundary.  At the place where they
touch, there is a little connection between the variable and the clause.
If a clause contains a variable $x_i$, then the gadget for variable $x_i$
approaches the triangle with an angle of $30^\circ$.  If a clause contains
$\bar{x}_i$, then the gadget for variable $x_i$ approaches the triangle
with an angle of $90^\circ$.  Since $G_{Exp}$ is planar, the variable and
clause gadgets can be connected to form a polygon $P$ with holes.

\begin{figure}[t]
   \begin{center}
   \input{clause.new.pstex_t}
   \end{center}
   \caption{The clause $(\bar{x}_h \lor x_i \lor \bar{x}_j)$.}
   \label{fi:clause.0}
\end{figure}

Notice that if the gadget of $x_i$ is set to true in a clause containing
$x_i$, or if the gadget of $x_i$ is set to false in a clause containing
$\bar{x}_i$, then two parallel chords from $x_i$'s gadget cross the
triangle.  These two parallel chords separate the three blue points in
the center of triangle from the remaining red points in the triangle.

We now show that $Exp(x)$ can be satisfied with exactly one true literal
per clause if and only if the blue and red points in $P$ can be separated
by exactly $kn$ non-intersecting chords.

First, suppose $Exp(x)$ can be satisfied with exactly one true literal
per clause.  We can separate the blue from the red points in each variable
$x_i$ with $k$ chords, depending on the truth value of $x_i$.  Since each
clause has exactly one true literal, only the corresponding variable has
two parallel chords that pass through the triangle.  So we have
separated all blue from all red points in the polygon using $kn$ chords.

On the other hand, suppose $kn$ chords suffice to separate the blue and
red points.  Each variable requires at least $k$ separating chords,
and the shape of the clause gadget imposes the constraint that
chords intersect no more than one variable gadget.
This implies that there are exactly $k$ chords per variable.  
% SL: now fixed:
%\xxx[Jeff]{What keeps us from
%using extra chords that intersect more than one variable gadget?}
Therefore each variable is set to true or false.  The blue points at
the center of each clause gadget are separated from the red points in
that gadget, which implies that each clause contains exactly one true
literal.

We still have to show that the size of the number of edges of the
polygon and the number of points inside is polynomial in $n$ and $m$.
Since $G_{Exp}$ is planar, it has a planar embedding with straight
line segments on an $O(n)\times O(n)$ unit grid \cite{dFPP90,Schnyder90}. 
Thus the length of each edge is $O(n+m)$.
Break each edge near the clause endpoint so that the incoming edges of
each clause form angles of 120 degrees.
The clause vertices are then easy to draw using a tiny clause gadget
with the openings aligned with incoming edges.
The variable vertices are represented by a point in the hole of 
the variable gadget, and the interior part of the variable is wrapped
around the edges in clockwise order. The width of the variable,
i.e. the distance between the inside and outside boundaries, is a small
constant $<1$.
The number of edges of the polygon is $O(n+m)$, and the length of
every edge is $O(n+m)$. 
The number of points in every edge is proportional to the length 
of the edge, so the total number of points is $O((n+m)^2)$.
\end{proof}

% \begin{figure}[htb]
%    \begin{center}
%    \input{variable.1.pstex_t}
%    \end{center}
%    \caption{Close up of a variable.}
%    \label{fi:var.1}
% \end{figure}

%We conjecture \xxx[Jeff]{Don't we?} that computing the minimum separating
%set of non-crossing chords remains NP-hard if the points lie in a simple
%polygon, a convex polygon, or even a circle.  We leave the proof or disproof
%of this conjecture as an open problem.

We conclude this section by remarking that between the results 
described in Theorems \ref{thm:strip}, \ref{thm:triangle} and  
\ref{thm:NP-hard} there is a gap that raises an
intriguing question:

\begin{open}
  What is the complexity of finding a minimal
  set of non-crossing chords that weakly separate two point 
  sets contained in the interior of
  \bi
    \item[(a)] a convex k-gon? (with k as part of the input)
    \item[(b)] a disk?
    \item[(c)] a simple polygon?
  \ei
\end{open}

\section*{Acknowledgement}

This research was initiated at the McGill Workshop on
Instance-Based Learning at Bellairs Research Institute, 
Jan.\ 31--Feb.\ 6, 2003.  The authors would like to thank the workshop
organizer Godfried Toussaint and the other workshop
participants, namely,
   Greg Aloupis,
   Prosenjit Bose,
   David Bremner,
%   Erik Demaine,
   Vida Dujmovi/'{c},
%   Jeff Erickson,
%   Ferran Hurtado,
%   John Iacono,
   Danny Krizanc,
%   Stefan Langerman,
%   Henk Meijer,
   Pat Morin,
%   Mark Overmars,
   Tom Shermer,
%   Sue Whitesides,
and
   David Wood for helpful
discussions and for providing a stimulating working environment.
%\xxx{Remove the names of authors from the preceding list.}

\bibliographystyle{abbrv}
\bibliography{whole-ham}

\end{document}
