# Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon

Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid

► To cite this version:

Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, Michiel Smid. Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. pp.56-71, 10.1007/978-3-319-28678-5_5. hal-01446264

HAL Id: hal-01446264

https://inria.hal.science/hal-01446264

Submitted on 25 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon *

Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari, and Michiel Smid

Carleton University, Ottawa, Canada

**Abstract.** Let $S$ be a finite set of points in the interior of a simple polygon $P$. A geodesic graph, $G_P(S, E)$, is a graph with vertex set $S$ and edge set $E$ such that each edge $(a, b) \in E$ is the shortest path between $a$ and $b$ inside $P$. $G_P$ is said to be *plane* if the edges in $E$ do not cross. If the points in $S$ are colored, then $G_P$ is said to be *properly colored* provided that, for each edge $(a, b) \in E$, $a$ and $b$ have different colors. In this paper we consider the problem of computing (properly colored) plane geodesic perfect matchings, Hamiltonian cycles, and spanning trees of maximum degree three.

# 1 Introduction

Let $S$ be a set of $n$ points in the interior of a simple polygon $P$ with $m$ vertices. For two points $a$ and $b$ in the interior of $P$, the geodesic $\pi(a, b)$, is defined to be the shortest path between $a$ and $b$ in the interior of $P$. A geodesic graph, $G_P(S, E)$, is a graph with vertex set $S$ and edge set $E$ such that each edge $(a, b) \in E$ is the geodesic $\pi(a, b)$ in $P$. If $P$ is a convex polygon, then $G_P$ is a straight-line geometric graph.

Let $\pi_1$ and $\pi_2$ be two, possibly self-intersecting, curves. We say that $\pi_1$ and $\pi_2$ cross if by traversing $\pi_1$ from one of its endpoints to the other endpoint we encounter a neighborhood of $\pi_1$ where $\pi_2$ intersects $\pi_1$ and switches from one side of $\pi_1$ to the other side [12]. We say that $\pi_1$ and $\pi_2$ are non-crossing if they do not cross. Two non-crossing curves can share an endpoint and can “touch” each other. If $\pi_1$ and $\pi_2$ are geodesics in a simple polygon, then they can intersect only once. They may have common line segments, but once they break apart, they do not meet again. See Figure 1. A geodesic graph is said to be *plane* if the edges in $E$ are pairwise non-crossing.

If the points in $S$ are colored, then a geodesic graph $G_P$ is said to be *properly colored* provided that, for each edge $(a, b) \in E$, $a$ and $b$ have different colors. For simplicity, in this paper we refer to a properly colored graph as a “colored graph”. Let $\{S_1, \dots, S_k\}$, where $k \ge 2$, be a partition of $S$. Let $K_P(S_1, \dots, S_k)$ be the complete multipartite geodesic graph on $S$ which has an edge between every point in $S_i$ and every point in $S_j$, for all $1 \le i < j \le k$. Imagine the points

<footnote>* Research supported by NSERC.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. (a) Two crossing geodesics, and (b) two non-crossing geodesics.</figcaption></figure>

in $S$ to be colored, such that all the points in $S_i$ have the same color, and for $i \neq j$, the points in $S_i$ have a different color from the points in $S_j$. We say that $S$ is a *k-colored* point set. Any colored geodesic graph, $G_P(S, E)$, is a subgraph of $K_P(S_1, \dots, S_k)$.

If $G_P$ is a perfect matching, a spanning tree, or a Hamiltonian cycle, we call it a *geodesic matching*, a *geodesic tree*, or a *geodesic Hamiltonian cycle*, respectively. A *colored geodesic matching* is a geodesic matching in $K_P(S_1, \dots, S_k)$. Similarly, a *colored geodesic tree* (resp. a *colored geodesic Hamiltonian cycle*) is a geodesic tree (resp. geodesic Hamiltonian cycle) in $K_P(S_1, \dots, S_k)$. A *plane colored geodesic matching* is a colored geodesic matching which is non-crossing. Similarly, a *plane colored geodesic tree* (resp. a *plane colored geodesic Hamiltonian cycle*) is a colored geodesic tree (resp. colored geodesic Hamiltonian cycle) which is non-crossing. Given a (colored) point set $S$ in the interior of a simple polygon $P$, we consider the problem of computing a plane (colored) geodesic matching, geodesic Hamiltonian cycle, and geodesic 3-tree in $K_P(S_1, \dots, S_k)$. A *t-tree* is a tree of maximum degree $t$. See Figure 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. (a) A plane colored geodesic matching, and (b) a plane colored geodesic 3-tree.</figcaption></figure>

## 1.1 Preliminaries

We say that a set $S$ of points in the plane is in *general position* if no three points of $S$ are collinear. Moreover, we say that a set $S$ of points in a simple polygon is *geodesically in general position* provided that, for any two points $a$ and $b$ in $S$, $\pi(a, b)$ does not contain any point of $S \setminus \{a, b\}$.

Toussaint [12] defined weakly-simple polygons—as a generalization of simple polygons—because in many situations concerned with geodesic paths the regions of interest are not simple but weakly-simple. A *weakly simple polygon* is defined as a closed polygonal chain $P = (p_1, \dots, p_m)$, possibly with repeated vertices,
such that every pair of distinct vertices of $P$ partitions $P$ into two non-crossing polygonal chains [12]. Alternatively, a closed polygonal chain $P$ is weakly simple if its vertices can be perturbed by an arbitrarily small amount such that the resulting polygon is simple. From the computational complexity point of view, almost all data structures and algorithms developed for simple polygons work for weakly simple polygons with only minor modifications that do not affect the time or space complexity bounds. Hereafter, we consider a weakly simple polygon to be a simple polygon.

For two points $a$ and $b$ in the interior of a simple polygon $P$, $\pi(a, b)$ consists of a sequence of straight-line segments. We refer to $a$ and $b$ as the *external vertices* of $\pi(a, b)$, and refer to the other vertices of $\pi(a, b)$ as *internal vertices*. Moreover, we refer to the line segment(s) of $\pi(a, b)$ which are incident on $a$ or $b$ as the *external segments* and the other segments as *internal segments*. In the special case where $\pi(a, b)$ is a straight-line segment, $\pi(a, b)$ does not have any internal vertex nor any internal segment.

**Observation 1** *The set of internal vertices of any geodesic in a simple polygon $P$ is a subset of the reflex vertices of $P$.*

The *oriented geodesic*, $\vec{\pi}(a, b)$, is the geodesic $\pi(a, b)$ which is oriented from $a$ to $b$. The *extended geodesic*, $\bar{\pi}(a, b)$, is obtained by extending the external segments of $\pi(a, b)$ till they meet the boundary of $P$. Let $a'$ and $b'$ be the points where $\pi(a, b)$ meet the boundary of $P$. Then, $\bar{\pi}(a, b)$ is equal to $\pi(a', b')$. An extended geodesic divides $P$ into two (weakly) simple polygons. See Figure 3.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** A color-balanced point set $S$ in the interior of a simple polygon $P$. (a) A balanced geodesic $\pi(a, b)$ with external vertices $a$ and $b$. (b) The extended geodesic $\bar{\pi}(a, b)$ divides $P$ into $P_1, P_2$, and partitions $S$ into $T_1, T_2$.</figcaption></figure>

Assume $S$ is partitioned into *color* classes, i.e., each point in $S$ is colored by one of the given colors. $S$ is said to be *color-balanced* if the number of points of each color is at most $\lfloor n/2 \rfloor$, where $n = |S|$. In other words, $S$ is color-balanced if no color is in strict majority. Moreover, $S$ is said to be *weakly color-balanced* if the number of points of each color is at most $\lfloor n/2 \rfloor$. Assume $S$ is color-balanced and is in the interior of a simple polygon $P$. Let $\pi$ be a geodesic in $P$. Let $P_1$ and $P_2$ be the (weakly) simple polygons on each side of the extended geodesic $\bar{\pi}$. Let $T_1$ and $T_2$ be the points of $S$ in $P_1$ and $P_2$, respectively. We say that $\pi$ is a *balanced geodesic* if both $T_1$ and $T_2$ are color-balanced and the number of
points in each of $T_1$ and $T_2$ is at most $\frac{2n}{3} + 1$. See Figure 3. The ham-sandwich geodesic (see [5]) is a balanced geodesic: given a set $R$ of red points and a set $B$ of blue points in a simple polygon $P$, a ham-sandwich geodesic is a geodesic which has its endpoints on the boundary of $P$ and has at most $|R|/2$ red points and at most $|B|/2$ blue points on each side.

By Observation 1, both endpoints of any internal segment of a ham-sandwich geodesic are reflex vertices of $P$. Thus, we have the following observation:

**Observation 2** Let $R$ and $B$ be two disjoint sets of points in a simple polygon $P$. Let $F$ be the set of reflex vertices of $P$. Let $\pi$ be a ham-sandwich geodesic for $R$ and $B$ in $P$. If $R \cup B \cup F$ is in general position, then

* the internal segments of $\pi$ do not contain any point of $R \cup B$.

* if $|R|$ (resp. $|B|$) is an even number, then the external segments of $\pi$ do not contain any point of $R$ (resp. $B$).

* if $|R|$ (resp. $|B|$) is an odd number, then exactly one of the external segments of $\pi$ contains exactly one point of $R$ (resp. $B$). Moreover, if both $|R|$ and $|B|$ are odd numbers, then the two points which are on $\pi$, belong to different external segments of $\pi$ (assuming $\pi$ is not a straight-line segment).

Bose et al. [5] presented an $O((n+m) \log m)$ expected-time randomized algorithm for finding a ham-sandwich geodesic. Their algorithm is optimal in the algebraic computation tree model.

## 1.2 Non-Crossing Structures in the Plane

Let $S$ be a set of points in general position in the plane. Let $K(S)$ be the complete straight-line geometric graph on $S$. One can compute a plane Hamiltonian cycle in $K(S)$ in the following way. Let $c$ be a point in $\mathbb{R}^2 \setminus S$ which is in the interior of the convex hull of $S$. Sort the points in $S$ radially around $c$, then connect each point to its successor. The resulting structure, say $H$, is a plane Hamiltonian cycle in $K(S)$. By removing any edge from $H$ a plane 2-tree is obtained. By picking every second edge of $H$ a plane perfect matching is obtained (assuming $|S|$ is an even number).

Hereafter, assume $S$ is partitioned into $\{S_1, \dots, S_k\}$, where $k \ge 2$, and the points in $S_i$ are colored $C_i$. Let $K(S_1, \dots, S_k)$ be the complete straight-line multipartite geometric graph on $S$. Observe that if $K(S_1, \dots, S_k)$ contains a plane Hamiltonian path, then $S$ is weakly color-balanced. The reverse may not be true; if $S$ is (weakly) color-balanced, it is not always possible to find a plane Hamiltonian path (or a plane 2-tree) in $K(S_1, \dots, S_k)$. See [1, 8] for examples. Kaneko [7] showed that if $k=2$ and $S$ is color-balanced, i.e., $|S_1| = |S_2|$, then $K(S_1, S_2)$ contains a plane 3-tree. Kano et al. [9] extended this result for $k \ge 2$: if $S$ is weakly color-balanced, then $K(S_1, \dots, S_k)$ contains a plane 3-tree.

A necessary and sufficient condition for the existence of a perfect matching (or colored matching) in $K(S_1, \dots, S_k)$ follows from a result of Sitton [11].

**Corollary 1.** Let $\{S_1, \dots, S_k\}$ be a partition of a point set $S$ in the plane, where $k \ge 2$ and $|S|$ is even. Then, $K(S_1, \dots, S_k)$ has a colored matching if and only if $S$ is color-balanced.
Aichholzer et al. [2], and Kano et al. [9] show that the same condition as in Corollary 1 is necessary and sufficient for the existence of a plane colored matching in $K(S_1, \dots, S_k)$:

**Theorem 1 (Aichholzer et al. [2], and Kano et al. [9]).** Let $\{S_1, \dots, S_k\}$ be a partition of a point set $S$ in the plane, where $k \ge 2$ and $|S|$ is even. Then, $K(S_1, \dots, S_k)$ has a plane colored matching if and only if $S$ is color-balanced.

In fact, they show something stronger. Aichholzer et al. [2] showed that any minimum-weight colored matching in $K(S_1, \dots, S_k)$, which minimizes the total Euclidean length of the edges, is plane. Kano et al. [9] presented a constructive proof for the existence of a plane colored matching in $K(S_1, \dots, S_k)$. Biniaz et al. [4] presented an algorithm which computes a plane colored matching in $K(S_1, \dots, S_k)$ optimally in $\Theta(n \log n)$ time.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** (a) A minimum-weight colored geodesic matching which is crossing. (b) A non-crossing matching in the plane, and (c) its geodesic mapping which is crossing. (d) A non-crossing geodesic matching.</figcaption></figure>

Although any minimum-weight colored matching in $K(S_1, \dots, S_k)$ is non-crossing, this is not always the case for any minimum-weight colored geodesic matching in $K_P(S_1, \dots, S_k)$, where the weight of a geodesic is defined to be the total Euclidean length of its line segments. Figure 4(a) shows a minimum-weight colored geodesic matching which is crossing.

As shown in Figures 4(b)-(d) if we map a non-crossing matching in the plane to a geodesic matching inside a simple polygon, then the resulting matching may cross. This is also the case for non-crossing Hamiltonian cycles and non-crossing trees. Therefore, in order to compute a non-crossing geodesic structure in a simple polygon, it may not be an option to compute a non-crossing structure in the plane first, and then map it to a geodesic structure in the polygon.

## 1.3 Our Contributions

We generalize the notion of non-crossing (colored) structures for the case when the points are in the interior of a simple polygon and the edges are geodesics. Note that the problem of computing a non-crossing (colored) structure for points in the plane is the special case when the simple polygon is convex.
Let $S$ be a set of $n$ points in a simple polygon $P$ with $m$ vertices. Let $K_P(S)$ be the complete geodesic graph on $S$. In Section 2, we show that $K_P(S)$ contains a plane geodesic Hamiltonian cycle. This also proves the existence of a plane geodesic matching and a plane geodesic 2-tree in $K_P(S)$. We show how to construct such a cycle in $O(m + n \log(n+m))$ time.

Let $\{S_1, \dots, S_k\}$, where $k \ge 2$, be a partition of $S$. Imagine the points in $S$ to be colored, such that all the points in $S_i$ have the same color, and for $i \ne j$, the points in $S_i$ have a different color from the points in $S_j$. In Section 3 we extend the result of Kano et al. [9] for geodesic 3-trees. We show that if $S$ is weakly color-balanced and $S \cup F$ is in general position, then $K_P(S_1, \dots, S_k)$ contains a plane geodesic 3-tree and it can be computed in $O(nm + n^2 \log(n+m))$ time. In Section 4, we prove that if $S$ is color-balanced and $S \cup F$ is in general position, then there exists a balanced geodesic for $S$ in $P$. Moreover, if $|S|$ is even, then there exists a balanced geodesic which partitions $S$ into two point sets each of even size. In either case, a balanced geodesic can be computed in $O((n+m) \log m)$ time. In Section 5 we compute a plane geodesic matching in $K_P(S_1, \dots, S_k)$ in $O(nm \log m + n \log n \log m)$ time by recursively finding balanced geodesics.

# 2 Plane Geodesic Hamiltonian Cycles

## 2.1 Sweep-Path Algorithm

Let $S$ be a set of $n$ points in the plane. In a *sweep-line algorithm*, an imaginary vertical line scans the plane from left to right. The sweep line meets the points in $S$ in the order determined by their $x$-coordinates. In a variant of the sweep-line algorithm, which is known as a *radial sweep algorithm*, an imaginary half-line, which is anchored at a point $s$ in the plane, scans the plane in counter-clockwise order around $s$. The radial sweep meets the points in $S$ in angular order around $s$. We extend the radial sweep algorithm for point set $S$ in the interior of a simple polygon $P$. In the new algorithm, which we call *sweep-path algorithm*, an imaginary path which is anchored at a vertex $s$ of $P$, scans $P$ in “counter-clockwise” order around $s$. It gives a “radial ordering” for the points in $S$.

The sweep-path algorithm runs as follows. Let $s$ be a vertex of $P$ such that $S \cup \{s\}$ is geodesically in general position. Let $t$ be a point which is initially at $s$. The algorithm moves $t$, in counter-clockwise order, along the boundary of $P$. See Figure 5(a). At each moment the sweep-path is the oriented geodesic $\vec{\pi}(s,t)$. The algorithm stops as soon as $t$ reaches its initial position, i.e., $s$. For two points $a, b \in S$ we say that $a \prec b$ if $\vec{\pi}(s,t)$ meets $a$ before $b$. Thus, the sweep-path algorithm defines a total ordering $S = (s_1, \dots, s_n)$ on the points in $S$ such that $s_i \prec s_j$, for all $1 \le i < j \le n$. See Figure 7(a). We show how to obtain $S$ in $O(m + n \log(n+m))$ time, where $m$ is the number of vertices of $P$.

Let $s$ be a vertex of $P$ such that $S \cup \{s\}$ is geodesically in general position. We start by constructing the *shortest path tree* for $s$, denoted by SPT($s$). This tree is defined to be the union of the shortest paths from $s$ to all vertices of $P$. Then, we construct the *shortest path map* for $s$, denoted by SPM($s$). The shortest path
<figure><img src="image_6.png" /><figcaption>**Fig. 5.** (a) The shortest path tree rooted at *s* (in bold) which is extended (by dashed lines) to form the shortest path map for *s*. (b) The skeleton tree of SPT(*s*) (in bold) which is enhanced by the vertices representing the regions in SPM(*s*).</figcaption></figure>

map for *s* is an enhancement of the shortest path tree rooted at *s*. See Figure 5(a).
Whereas the shortest path tree encodes the shortest path from every vertex of *P*
to *s*, the shortest path map encodes the shortest path from every point inside *P*
to *s*. Given SPT(*s*), the SPM(*s*) can be produced by partitioning the funnels of
all edges of *P* in SPT(*s*). For each edge of *P*, we partition the funnel associated
with it by extending the funnel edges. This partitions the funnel into triangular
sectors (regions), each with a distinguished vertex called *apex*. The resulting
subdivision is SPM(*s*). For a particular triangular region *R* in SPM(*s*) let *a*(*R*)
denote the apex of *R* (Figure 5(a)). For any point *p* inside *R* the *predecessor* of
*p* along $\vec{\pi}(*p*)$ is *a*(*R*). Moreover, all points of *R* have the same internal vertex
sequence in their shortest path to *s*.

Let $T$ be the skeleton tree obtained from SPT($s$) by removing its leaves (Figure 5(b)). $T$ contains the apex of all regions in SPM($s$). For each region $R$ in SPM($s$) create a vertex which represents $R$, then, connect that vertex as a child to $a(R)$ in $T$. See Figure 5(b). We order the children of each internal vertex $v \in T$ as follows. Let $P(v)$ be the union of the regions having $v$ as their apex. See Figure 6. Note that $P(v)$ is the union of a sequence of adjacent triangular regions all anchored at $v$, where $v$ is a vertex of the boundary of $P(v)$. We order the children of $v$ in counter-clockwise order.

We run depth-first-search on $T$ to obtain an ordering $\mathcal{R} = (R_1, R_2, \dots)$ on the regions of SPM($s$). See Figure 5(b) and Figure 6. Then, we locate the points of $S$ in SPM($s$). For each region $R$ in SPM($s$), let $L(R)$ be the list of points of $S$ within $R$ which are sorted counter-clockwise around $a(R)$. By replacing each $R_i$ in $\mathcal{R}$ with $L(R_i)$ the desired ordering $S$ is obtained. See Figure 7(a).

SPM($s$) has $O(m)$ size and can be computed in $O(m)$ time in a triangulated
polygon using the algorithm of Guibas et al. [6]. A planar point location data
structure for SPM($s$) can be constructed in $O(m)$ time and answers point loca-
tion queries in $O(\log m)$ time [10]. Thus, we can locate the points of $S$ in SPM($s$)
in $O(m + n \log m)$ time. Making $T$ to be an ordered tree takes $O(m)$ time by the
construction of SPM($s$) [6]. Sorting the points of $S$ takes $O(n \log n)$ time for all
regions. The depth first search algorithm runs in $O(m)$ time, and substituting
each $R_i$ with $L(R_i)$ takes $O(m + n)$ time. Thus, the total running time of the
sweep-path algorithm is $O(m + n \log(n + m))$.
<figure><img src="image_7.png" /><figcaption>Fig. 6. The skeleton tree T (in bold) which is enhanced by the vertices representing the regions of SPM(s). For each v ∈ T, the children of v are ordered counter-clockwise.</figcaption></figure>

See the full version of the paper for the proof of the following lemma.

**Lemma 1.** Let $S = (s_1, \dots, s_n)$ be the ordering of the points in $S$ obtained by the sweep-path algorithm. Let $s_i, s_j, s_k$ and $s_l$ be points in $S$ such that $1 \le i < j \le k < l \le n$. Then, $\pi(s_i, s_j)$ and $\pi(s_k, s_l)$ are non-crossing.

## 2.2 Plane Geodesic Hamiltonian Cycles

Given a set $S$ of $n$ points in a simple polygon $P$ with $m$ vertices, in this section we show how to compute a plane geodesic Hamiltonian cycle on $S$.

A set $Q \subseteq P$ is called geodesically (or relative) convex if for any pair of points $a, b \in Q$ the geodesic between $a$ and $b$ in $P$, also lies in $Q$. The geodesic hull (or relative convex hull) of $S$ in $P$, denoted by $GH(S)$, is defined to be the smallest geodesically convex set in $P$ that contains $S$. Toussaint [12] showed that the geodesic hull of $S$ in $P$ is a weakly simple polygon, and can be computed in $O(m + n \log(n + m))$ time. Since for any two points $a$ and $b$ in $S$, $\pi(a, b)$ lies in $GH(S)$, without loss of generality, we assume that $P = GH(S)$. Let $s_0$ be a point of $S$ on $GH(S)$. We run the sweep-path algorithm for $S \setminus \{s_0\}$ in $GH(S)$. It gives an ordering $S = (s_1, \dots, s_{n-1})$ for the points in $S \setminus \{s_0\}$. We compute the following geodesic Hamiltonian cycle $C$ (see Figure 7),

$$C = \{(s_i, s_{i+1}) : 1 \le i \le n-2\} \cup \{(s_0, s_1), (s_0, s_{n-1})\}.$$

Note that $s_1$ and $s_{n-1}$ are the neighbors of $s_0$ on $GH(S)$. Therefore, $(s_0, s_1)$ and $(s_0, s_{n-1})$ are non-crossing and do not cross $(s_i, s_{i+1})$ for all $1 \le i \le n-2$. In addition, by Lemma 1 for $1 \le i < j \le k < l \le n-1$, $(s_i, s_j)$ and $(s_k, s_l)$ are non-crossing. This proves the planarity of $C$. By removing any edge from $C$, a plane geodesic 2-tree for $S$ is obtained. By picking every second edge of $C$, a plane geodesic matching for $S$ is obtained. Computing $GH(S)$ and running the sweep-path algorithm takes $O(m + n \log(n + m))$ time. Note that even if $S$ is not geodesically in general position, one can compute $C$ by simply modifying the sweep-path algorithm. Therefore, we have proved the following theorem:

**Theorem 2.** Let $S$ be a set of $n$ points in a simple polygon with $m$ vertices. Then, a plane geodesic Hamiltonian cycle, a plane geodesic 2-tree, and a plane geodesic matching for $S$ can be computed in $O(m + n \log(n + m))$ time.
<figure><img src="image_8.png" /><figcaption>Fig. 7. (a) Points of S which are sorted by the sweep-path algorithm. (b) A plane geodesic Hamiltonian cycle (assuming $s_0$ is a point of S).</figcaption></figure>

## 3 Plane Geodesic Trees

Let S be a set of n points in the interior of a simple polygon P with m vertices. Let {$S_1, \dots, S_k$} be a partition of S, where the points in $S_i$ are colored $C_i$. In this section we show that if S is weakly color-balanced and geodesically in general position, then there exists a plane colored geodesic 3-tree on S.

If $k \ge 4$, then by using the technique in the proof of Lemma 2 in [4], in $O(n)$ time we can reduce S to a weakly color-balanced point set with three colors such that any plane colored geodesic tree on the resulting 3-colored point set is also a plane colored geodesic tree on S. Therefore, from now on we assume that S is weakly color-balanced and its points colored by two or three colors. Let $CH(S)$ denote the convex hull of S. For a (geodesic) tree T and a given vertex s in T, let $d_T(s)$ denote the degree of s in T. Kano et al. [9] proved the following lemma and theorems for colored points in the plane. We adjusted the statements according to our setting and definitions.

**Lemma 2 (Kano et al. [9]).** Let $(s_1, \dots, s_n)$ be a sequence of $n \ge 3$ points colored with at most 3 colors<fnref n="1" /> such that $s_1$ and $s_n$ have the same color. If {$s_1, \dots, s_n$} is weakly color-balanced, then there exists an even number p, $2 \le p \le n-1$, such that both {$s_1, \dots, s_p$} and {$s_{p+1}, \dots, s_n$} are weakly color-balanced.

**Theorem 3 (Kano et al. [9]).** Let S be a set of points in general position in the plane which are colored red and blue. Let R be the set of red points and B the set of blue points. Let s be a vertex of CH(S). If one of the following conditions holds, then there exists a plane colored 3-tree, T, on S such that $d_T(s) = 1$.

(i) $|B| = 1, 1 \le |R| \le 3$, and $s \in R$,

(ii) $2 \le |B|, |R| = |B| + 2$, and $s \in R$,

(iii) $2 \le |B| \le |R| \le |B| + 1$.

**Theorem 4 (Kano et al. [9]).** Let S be a weakly color-balanced point set in general position in the plane which is colored by three colors. Let s be a vertex of CH(S). Then, there exists a plane colored 3-tree, T, on S such that $d_T(s) = 1$.

<footnote n="1">¹ Actually, they prove the statement of the theorem for 2- and 3-colored point sets.</footnote>
We extend Theorem 3 and Theorem 4 to prove the existence of plane geodesic trees on the colored points in the interior of a simple polygon. We adjust the proofs given in [9] to our setting, skipping the details.

**Theorem 5.** Let $S$ be a set of $n$ points which is geodesically in general position in a simple polygon $P$ with $m$ vertices. Assume the points in $S$ are colored red and blue. Let $R$ be the set of red points and $B$ the set of blue points. Let $s$ be a vertex of $GH(S)$. If one of the following conditions holds, then in $O(nm+n^2 \log(n+m))$ time, one can compute a plane colored geodesic 3-tree, $T$, with vertex set $S$ in $P$ such that $T$ is rooted at $s$ and $d_T(s) = 1$.

(i) $|B| = 1, 1 \le |R| \le 3$, and $s \in R$,

(ii) $2 \le |B|, |R| = |B| + 2$, and $s \in R$,

(iii) $2 \le |B| \le |R| \le |B| + 1$.

*Proof.* The proof is by construction. Since for any two points $a$ and $b$ in $S$, $\pi(a, b)$ lies in $GH(S)$, without loss of generality, we may assume that $P = GH(S)$. If Condition (i) holds, the proof is trivial. Hence, assume that (ii) or (iii) holds. Let $x$ and $y$ be the left and the right neighbors of $s$ on the boundary of $GH(S)$. If $s$ and a neighboring vertex, say $x$, have distinct colors, then let $T_1$ be the tree obtained recursively on $S \setminus \{s\}$ which is rooted at $x$. Observe that $x$ is a vertex of $GH(S \setminus \{s\})$ and $\pi(s, x)$ does not intersect $GH(S \setminus \{s\})$. Then, $T = T_1 + \pi(s, x)$ is the desired tree.

<figure><img src="image_9.png" /><figcaption>**Fig. 8.** Illustration of Theorem 5: (a) $|R| = |B| + 2, s \in R$, and (b) $|R| = |B| + 1, s \in B$.</figcaption></figure>

If $s, x$, and $y$ have the same color, then let $S = (s_1, \dots, s_{n-1})$, where $s_1 = x$ and $s_{n-1} = y$, be the ordering of the points in $S \setminus \{s\}$ obtained by the sweep-path algorithm around $s$. See Figure 8(a). If $s \in B$, then let $S = (s_1, \dots, s_n)$, where $s_1 = s, s_2 = x$, and $s_n = y$. See Figure 8(b). In either case—$s \in R$ or $s \in B$—by Lemma 2 there exists an element $s_p$, with $p$ even, such that if $S_1$ and $S_2$ be the points of $S$ on each side of $\pi(s, s_p)$ (not including $s$ and $s_p$), then both $S_1 \cup \{s_p\}$ and $S_2$ are weakly color-balanced. Moreover, each of $S_1 \cup \{s_p\}$ and $S_2 \cup \{s_p\}$ satisfies one of the conditions (i), (ii), or (iii). Observe that $\pi(s, s_p)$ does not cross any of $GH(S_1 \cup \{s_p\})$ and $GH(S_2 \cup \{s_p\})$. In addition, $s_p$ is a vertex of both $GH(S_1 \cup \{s_p\})$ and $GH(S_2 \cup \{s_p\})$. Let $T_1$ (resp. $T_2$) be the tree obtained recursively on $S_1 \cup \{s_p\}$ (resp. $S_2 \cup \{s_p\}$) which is rooted at $s_p$. Since $d_{T_1}(s_p) = 1$ and $d_{T_2}(s_p) = 1$, $T = T_1 + T_2 + \pi(s, s_p)$ is the desired tree.
Computing the geodesic hull and running the sweep-path algorithm take $O(m+n \log(n+m))$ time. In the worst case, we recurse $O(|S|)$ times. Thus, the total running time of the algorithm is $O(nm+n^2 \log(n+m))$. $\square$

**Theorem 6.** Let $S$ be a 3-colored point set of size $n$ which is geodesically in general position in a simple polygon $P$ with $m$ vertices. Let $s$ be a vertex of $GH(S)$. If $S$ is weakly color-balanced, then in $O(nm + n^2 \log(n+m))$ time, we can compute a plane colored geodesic 3-tree, $T$, with vertex set $S$ in $P$ such that $T$ is rooted at $s$ and $d_T(s) = 1$.

*Proof.* Assume the points in $S$ are colored red, green, and blue. Let $R$, $G$, and $B$ be the set of red, green, and blue colors, respectively. Assume that $|B| \le |G| \le |R|$. The proof is by construction. If $|R| = \lceil|S|/2\rceil$, we assume that $G$ and $B$ have the same color and solve the problem by Theorem 5. Assume that $|R| \le \lceil|S|/2\rceil - 1$. Observe that in this case $S \setminus \{s\}$ is weakly color-balanced. Let $x$ and $y$ be the left and the right neighbors of $s$ on the boundary of $GH(S)$. If $s$ and a neighbor vertex, say $x$, have distinct colors, then let $T_1$ be the tree obtained recursively on $S \setminus \{s\}$ which is rooted at $x$. Observe that $x$ is a vertex of $GH(S \setminus \{s\})$ and $\pi(s, x)$ does not intersect $GH(S \setminus \{s\})$. Then, $T = T_1 + \pi(s, x)$ is the desired tree.

If $s$, $x$, and $y$ have the same color, then let $S = (s_1, \dots, s_{n-1})$, where $s_1 = x$ and $s_{n-1} = y$, be the ordering of points in $S \setminus \{s\}$ obtained by the sweep-path algorithm on $s$. By Lemma 2 there exists an element $s_p$, with $p$ even, such that if $S_1$ and $S_2$ be the points of $S$ on each side of $\pi(s, s_p)$, then both $S_1 \cup \{s_p\}$ and $S_2$ are weakly color-balanced. Since $|R| \le \lceil|S|/2\rceil - 1$, $S_2 \cup \{s_p\}$ is also color-balanced. Moreover, $\pi(s, s_p)$ does not cross any of $GH(S_1 \cup \{s_p\})$ and $GH(S_2 \cup \{s_p\})$. Let $T_1$ (resp. $T_2$) be the tree obtained recursively on $S_1 \cup \{s_p\}$ (resp. $S_2 \cup \{s_p\}$) which is rooted at $s_p$. Since $d_{T_1}(s_p) = 1$ and $d_{T_2}(s_p) = 1$, $T = T_1 + T_2 + \pi(s, s_p)$ is the desired tree.

As in the proof of Theorem 5, the running time is $O(nm+n^2 \log(n+m))$. $\square$

# 4 Balanced Geodesics

Let $S$ be set of $n \ge 3$ points in the interior of a simple polygon $P$ with $m$ vertices. Let $F$ be the set of reflex vertices of $P$. Let $\{S_1, \dots, S_k\}$ be a partition of $S$, where the points in $S_i$ are colored $C_i$. Assume $S$ is color-balanced. Recall that a balanced geodesic has its endpoints on the boundary of $P$ and partitions $S$ into two point sets $T_1$ and $T_2$, such that both $T_1$ and $T_2$ are color-balanced and $\max\{|T_1|, |T_2|\} \le \frac{2n}{3} + 1$. We prove that if $S \cup F$ is in general position, then there exists a balanced geodesic for $S$ in $P$. In fact, we show how to find such a balanced geodesic in $O((n+m) \log m)$ time by using a similar idea as in [4].

**Theorem 7 (Balanced Geodesic Theorem).** Let $S$ be a color-balanced point set of $n \ge 3$ points which is in the interior of a simple polygon $P$ with $m$ vertices. Let $F$ be the set of reflex vertices of $P$. If $S \cup F$ is in general position, then in $O((n+m) \log m)$ time we can compute a geodesic $\pi$ such that
1. $\pi$ does not contain any point of $S$.

2. $\pi$ partitions $S$ into two point sets $T_1$ and $T_2$, where

(a) both $T_1$ and $T_2$ are color-balanced,

(b) both $T_1$ and $T_2$ contains at most $\frac{2}{3}n + 1$ points,

(c) if $n$ is even, then both $T_1$ and $T_2$ have an even number of points.

*Proof.* Let $\{S_1, \dots, S_k\}$ be the partition of $S$ such that the points in $S_i$ are colored $C_i$. We differentiate between three cases when $k=2, k=3$, and $k \ge 4$.

If $k=2$, then $|S_1| = |S_2|$. Without loss of generality assume the points in $S_1$ are colored red and the points in $S_2$ are colored blue. Let $\pi$ be a ham-sandwich geodesic of $S$ in $P$. By Observation 2, if $|S_1|$ and $|S_2|$ are even numbers then $\pi$ does not contain any point of $S$ and hence it is a desired balanced geodesic. If $|S_1|$ and $|S_2|$ are odd, then one of the external segments of $\pi$ contains a red point, say $r$, and the other external segment contains a blue point, say $b$. We adjust the external segments of $\pi$ (by slightly moving its external vertices on $P$) such that both $r$ and $b$ lie on the same side of $\pi$. If $\pi$ is a straight line segment, then we move $\pi$ slightly such that both $r$ and $b$ lie on the same side of $\pi$. In either case, $\pi$ is a desired balanced geodesic.

If $k \ge 4$, then by using the technique in the proof of Lemma 2 in [4], in $O(|S|)$ time we can reduce $S$ to a color-balanced point set with three colors such that any balanced geodesic for the resulting 3-colored point set is also a balanced geodesic for $S$. Therefore, from now on we assume that $S$ color-balanced and its points are colored by three colors, i.e., $k=3$.

<figure><img src="image_10.png" /><figcaption>**Fig. 9.** Illustrating Theorem 7. The blue points in $X$ are indicated by bounding circles. The ham-sandwich geodesic is in dashed lines. The geodesic $\pi$, with endpoints $p$ and $q$, is a balanced geodesic when: (a) $|R|$ is even, and (b) $|R|$ is odd.</figcaption></figure>

Let the points in $S$ to be colored red, green, and blue. Let $R$, $G$, and $B$ denote the set of red, green, and blue points, respectively. Without loss of generality assume that $1 \le |B| \le |G| \le |R|$. Since $P$ is color-balanced, $|R| \le \lfloor \frac{n}{2} \rfloor$. Let $X$ be an arbitrary subset of $B$ such that $|X| = |R| - |G|$; note that $X = \emptyset$ when $|R| = |G|$, and $|X| = |B|$ when $|R| = \frac{n}{2}$ (when $n$ is even). Let $Y = B - X$. Let $\pi$ be a ham-sandwich geodesic for $R$ and $G \cup X$ in $P$ (by imagining that the points in $G \cup X$ have the same color). Let $T_1$ and $T_2$ denote the set of points of $S$ on each side of $\pi$; see Figure 9(a). Let $R_1, G_1$, and $B_1(= X_1 \cup Y_1)$ be the set of red, green, and blue points in $T_1$ such that $X_1 = X \cap T_1$ and $Y_1 = Y \cap T_1$. Similarly, we define $R_2, G_2, B_2, X_2$, and $Y_2$ as subsets of $T_2$.
If $|R|$ is an even number, then $\pi$ does not contain any point of $R \cup G \cup X$. If $\pi$ contains any point $y \in Y$, then by Observation 2, $y$ is on an external segment of $\pi$. We adjust that external segment (by slightly moving its external vertex on either side) such that it does not contain any point of $S$. If $|R|$ is an odd number, then $\pi$ contains a point $x \in R$ and a point $y \in G \cup X$; see Figure 9(b). By Observation 2, $x$ and $y$ are on different external segments of $\pi$ (unless $\pi$ is a straight line segment). In this case, without loss of generality, assume $|B_2| \ge |B_1|$. We adjust the external segments of $\pi$ slightly such that $x$ and $y$ lie on the same side as $T_2$, i.e., $T_2 = T_2 \cup \{x, y\}$ (if $\pi$ is a straight-line segment, then we move $\pi$ slightly such that $T_2 = T_2 \cup \{x, y\}$); see Figure 9(b). We prove that $\pi$ satisfies the statement of the theorem. In either case we have $|R_1| = \lfloor|R|/2\rfloor$, $|R_2| = \lceil|R|/2\rceil$, $|G_1| + |X_1| = |R_1|$, and $|G_2| + |X_2| = |R_2|$. Therefore,

$$ 
\begin{aligned}
|T_1| &\ge |R_1| + |G_1| + |X_1| = 2\lfloor|R|/2\rfloor, \\
|T_2| &\ge |R_2| + |G_2| + |X_2| = 2\lceil|R|/2\rceil.
\end{aligned} 
\quad (1) $$

By the ham-sandwich geodesic we have $|G_1| \le |R_1|$. This and Inequality (1) imply that $|G_1| \le |R_1| = \lfloor|R|/2\rfloor \le |T_1|/2$. Similarly, we have $|G_2| \le |R_2| = \lceil|R|/2\rceil \le |T_2|/2$. In order to prove that $T_1$ and $T_2$ are color-balanced, we have to show that $|B_1| \le |T_1|/2$ and $|B_2| \le |T_2|/2$. Let $t_1$ and $t_2$ be the total number of red and green points in $T_1$ and $T_2$, respectively; that is $t_1 = |R_1 \cup G_1|$ and $t_2 = |R_2 \cup G_2|$. Then,

$$ |T_1| = t_1 + |B_1| \quad \text{and} \quad |T_2| = t_2 + |B_2|. \quad (2) $$

In addition,

$$ 
\begin{aligned}
t_1 &= |R_1| + |G_1| \\
&= |R_1| + (|R_1| - |X_1|) \\
&\ge 2|R_1| - |X_1| \\
&= 2\lfloor|R|/2\rfloor - (|R| - |G_1|) \\
&= \begin{cases} |G_1| & \text{if } R \text{ is even} \\ |G_1| - 1 & \text{if } R \text{ is odd,} \end{cases}
\end{aligned} 
\quad t_2 = |R_2| + |G_2| \\
&= |R_2| + (|R_2| - |X_2|) \\
&\ge 2|R_2| - |X_2| \\
&= 2\lceil|R|/2\rceil - (|R| - |G_1|) \\
&= \begin{cases} |G_1| & \text{if } R \text{ is even} \\ |G_1| + 1 & \text{if } R \text{ is odd.} \end{cases} 
\quad (3) $$

Recall that $|B| \le |G|$. Equation (2) and Inequality (3) imply that $|B_2| \le |T_2|/2$. If $|R|$ is an even number, then Equation (2) and Inequality (3) imply that $|B_1| \le |T_1|/2$. If $|R|$ is an odd number, then by assumption we have $|B_1| \le |B_2|$; this implies that $|B_1| \le |B| - 1$. Again by Equation (2) and Inequality (3) we have $|B_1| \le |T_1|/2$. Therefore, both $T_1$ and $T_2$ are color-balanced.

Now we prove the upper bound on the sizes of $T_1$ and $T_2$. By Inequality (1) both $|T_1|$ and $|T_1|$ are at least $2\lfloor|R|/2\rfloor$. This implies that,

$$ \max\{|T_1|, |T_2|\} \le n - 2\lfloor\frac{|R|}{2}\rfloor \le n - 2(\frac{|R| - 1}{2}) \le n - |R| + 1. $$

Since $R$ is the largest color class, $|R| \ge \lceil\frac{n}{3}\rceil$. Therefore, $\max\{|T_1|, |T_2|\} \le n - \frac{n}{3} + 1 = \frac{2n}{3} + 1$.
The ham-sandwich geodesic $\pi$ for $R$ and $G \cup X$ in $P$ can be computed in $O((n+m) \log m)$ time. Adjusting the external segments of $\pi$ takes constant time. Thus, the total running time is $O((n+m) \log m)$.

See the full version of the paper for the proof of case (c), when $n$ is even. □

## 5 Plane Colored Geodesic Matchings

Let $S$ be a set of $n$ points, with $n$ an even number, which is in the interior of a simple polygon $P$ with $m$ vertices. Let $F$ be the set of reflex vertices of $P$. Let $\{S_1, \dots, S_k\}$, where $k \ge 2$, be a partition of $S$ such that the points in $S_i$ are colored $C_i$. Assume $S$ is color-balanced. In this section we show that if $S \cup F$ is in general position, then $K_P(S_1, \dots, S_k)$ contains a plane colored geodesic matching. In fact we show how to compute such a matching. If $k \ge 4$, by the technique of Lemma 2 in [4], in $O(n)$ time we can reduce $S$ to a color-balanced point set with three colors such that any plane colored geodesic matching on the resulting 3-colored point set is also a plane colored geodesic matching on $S$. Thus, we assume that $S$ color-balanced and its points are colored by at most three colors.

As in Theorem 6, we can adjust the technique used by Kano et al. [9]—for computing a non-crossing colored matching in the plane—to our setting. As a result we can compute a plane colored geodesic matching for $S$ in $P$ in $O(nm + n^2 \log(n+m))$ time.

Now we present an algorithm that computes a plane colored geodesic matching by recursively applying Balanced Geodesic Theorem as follows. By Theorem 7, we can find a balanced geodesic $\pi$ that partitions $P$ into simple polygons $P_1$ and $P_2$ containing point sets $T_1$ and $T_2$ such that both $T_1$ and $T_2$ are color-balanced with an even number of points, and $\max\{|T_1|, |T_2|\} \le \frac{2n}{3} + 1$. Let $M_1$ (resp. $M_2$) be a plane colored geodesic matching for $T_1$ (resp. $T_2$) in $P_1$ (resp. $P_2$). Since $P_1$ and $P_2$ are separated by $\pi$, $M_1 \cup M_2$ is a plane colored geodesic matching for $S$. Therefore, in order to compute a plane colored geodesic matching for $S$ in $P$, we compute a balanced geodesic for $S$ in $P$, and then recursively compute plane colored geodesic matchings for $T_1$ in $P_1$ and for $T_2$ in $P_2$.

Let $T(n, m)$ denote the running time of the recursive algorithm on $S$ and $P$, where $|S| = n$ and $|P| = m$. By Theorem 7, the balanced geodesic $\pi$ can be computed in $O((n+m) \log m)$ time. The size of each of $P_1$ and $P_2$ is at most the size of $P$, and hence the recursions take $T(|T_1|, m)$ and $T(|T_2|, m)$ time. Thus, the running time of the algorithm can be expressed by the following recurrence:

$$T(n, m) = T(|T_1|, m) + T(|T_2|, m) + O((n+m) \log m).$$

Since $|T_1|, |T_2| \le \frac{2n}{3} + 1$ and $|T_1| + |T_2| = n$, this recurrence solves to

$$T(n, m) = O(nm \log m + n \log n \log m).$$

**Theorem 8.** Let $S$ be a color-balanced point set of size $n$, with $n$ even, in a simple polygon $P$ with $m$ vertices, whose reflex vertex set is $F$. If $S \cup F$ is in general position, then a plane colored geodesic matching for $S$ in $P$ can be computed in $\min\{O(nm + n^2 \log(n+m)), O(nm \log m + n \log n \log m)\}$ time.
**Remark 1:** By using the geodesic-preserving polygon simplification method of [3], the running time of any algorithm presented in this paper as $O(f(n, m))$ can be stated as $O(m + f(n, r))$, where *r* is the number of reflex vertices of *P*.

**Remark 2:** In Section 3, in each recursion step we run the sweep-path algorithm to sort the points around $s_p$. Having a semi-dynamic data structure for maintaining the geodesic hull which supports point deletions in $O(\text{polylog}(nm))$ worst case time, we can avoid the repetitive sorting. This would improve the running time for computing a plane colored geodesic 3-tree and a plane colored geodesic matching to $O((n+m)\text{polylog}(nm))$.

## References

1. M. Abellanas, J. Garcia-Lopez, G. Hernández-Peñalver, M. Noy, and P. A. Ramos. Bipartite embeddings of trees in the plane. *Discrete Applied Mathematics*, 93(2-3):141–148, 1999.

2. O. Aichholzer, S. Cabello, R. F. Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado, and D. R. Wood. Edge-removal and non-crossing configurations in geometric graphs. *Discrete Mathematics & Theoretical Computer Science*, 12(1):75–86, 2010.

3. O. Aichholzer, T. Hackl, M. Korman, A. Pilz, and B. Vogtenhuber. Geodesic-preserving polygon simplification. In *Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC)*, pages 11–21, 2013.

4. A. Biniaz, A. Maheshwari, S. C. Nandy, and M. Smid. An optimal algorithm for plane matchings in multipartite geometric graphs. *To appear in Algorithms and Data Structures Symposium (WADS’15)*, 2015.

5. P. Bose, E. D. Demaine, F. Hurtado, J. Iacono, S. Langerman, and P. Morin. Geodesic ham-sandwich cuts. *Discrete & Computational Geometry*, 37(3):325–339, 2007.

6. L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. *Algorithmica*, 2:209–233, 1987.

7. A. Kaneko. On the maximum degree of bipartite embeddings of trees in the plane. In *Japan Conference on Discrete and Computational Geometry, JCDCG*, pages 166–171, 1998.

8. A. Kaneko and M. Kano. Discrete geometry on red and blue points in the plane—a survey. In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, *Discrete and Computational Geometry*, volume 25 of *Algorithms and Combinatorics*, pages 551–570. Springer Berlin Heidelberg, 2003.

9. M. Kano, K. Suzuki, and M. Uno. Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane. In *16th Japanese Conference on Disc. Comp. Geom. and Graphs, JCDCGG*, pages 96–111, 2013.

10. D. G. Kirkpatrick. Optimal search in planar subdivisions. *SIAM J. Comput.*, 12(1):28–35, 1983.

11. D. Sitton. Maximum matchings in complete multipartite graphs. *Furman University Electronic Journal of Undergraduate Mathematics*, 2:6–16, 1996.

12. G. T. Toussaint. Computing geodesic properties inside a simple polygon. *Revue D’Intelligence Artificielle*, 3(2):9–42, 1989.