Davood Bakhshesh
email: dbakhshesh@gmail.com

Mohammad Farshi
email: mfarshi@yazd.ac.ir.

Some properties of continuous Yao graph

Keywords: t-spanner, Region-fault tolerant spanner, Continuous Yao graph, Self-approaching graph

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.

Introduction

Let S be a set of n points in R d and let t ≥ 1 be a real number. A geometric graph is an edge-weighted graph on S ⊆ R d such that the weight of each edge is the Euclidean distance between its endpoints. A geometric graph G with vertex set S is called a t-spanner for S, if for each two points p and q in S, there exists a path Q in G between p and q whose length is at most t times |pq|, the Euclidean distance between p and q. The length of a path is defined to be the sum of the lengths, or weight, of all edges on the path. The path Q is called a t-spanner path (or t-path) between p and q. We denote the length of path Q by |Q|. The stretch factor (or dilation) of G is the smallest value of t for which G is a tspanner. The t-spanners were introduced by Peleg and Schäffer [START_REF] Peleg | Graph spanners[END_REF] in the scope of distributed computing and, then, by Chew [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF] in the scope of computational geometry. The t-spanners are applicable in many scopes such as graph theory, network topology design, distributed systems, robotics. We refer the reader to [START_REF] Chandra | New sparseness results on graph spanners[END_REF][START_REF] Eppstein | Spanning trees and spanners[END_REF][START_REF] Lukovszki | New results on geometric spanners and their applications[END_REF][START_REF] Smid | Closest point problems in computational geometry[END_REF] for reading about the t-spanners and their applications.

The problem of efficient construction of a t-spanner for a given point set and a constant t > 1 has been studied extensively. One can see the major algorithms for building spanners in the book by Narasimhan and Smid [START_REF] Narasimhan | Geometric spanner networks[END_REF].

The Yao graph used by Andrew Yao to construct Euclidean minimum spanning tree on high-dimensional Euclidean space [START_REF] Yao | On constructing minimum spanning trees in k-dimensional spaces and related problems[END_REF]. For a set S of points in the plane, the Yao graph Y k , for k ≥ 2, is defined as follows. At each point u ∈ S, we draw k cones with apex at u and angle 2π k . For each point u ∈ S and cone C, we add an edge between u and the closest point to u in C. If one chooses k sufficiently large, the Yao graph becomes a t-spanner.

In 2014, Barba et al. [START_REF] Barba | Continuous Yao graphs[END_REF] introduced the continuous Yao graph as a variation of Yao graph. The continuous Yao graph cY (θ) with vertex set S and angle θ defined as follows: For each p, q ∈ S, we add an edge from p to q in cY (θ) if there exists a θ-cone, a cone with aperture θ, with apex at p such that q is the closest point to p inside this θ-cone. In continuous Yao graph, for each u ∈ S, we rotate a θ-cone with apex u around u continuously, and connect u to the closest point inside the θ-cone during this rotation. They showed that cY (θ) has stretch factor at most 1/(1-2sin(θ/4)) for 0 < θ < 2π/3. Unlike Yao graphs that always have a linear number of edges for any constant k, in the worst case, continuous Yao graphs may have a quadratic number of edges. Since cY (θ) ⊆ cY (γ) for any θ ≥ γ, the continuous Yao graphs are useful in potential applications that require scalability. Moreover, when some rotations apply on the input point set the continuous Yao graphs are invariant [START_REF] Barba | Continuous Yao graphs[END_REF].

One of the useful properties of a network is fault tolerance that is after one or more vertices or edges fail, the remaining graph is still a good network of alive vertices. In particular, a graph G = (S, E) is called k-vertex fault-tolerant t-spanner [START_REF] Levcopoulos | Improved algorithms for constructing fault-tolerant spanners[END_REF] for S, denoted by (k, t)-VFTS for a given real number t ≥ 1 and non-negative positive integer k, if for each set S ⊆ S with cardinality of at most k, the graph G\S is a t-spanner for S\S . Also, G is called a kedge fault-tolerant t-spanner [START_REF] Levcopoulos | Improved algorithms for constructing fault-tolerant spanners[END_REF] for S, denoted by (k, t)-EFTS, if for each set E ⊆ E with cardinality at most k and for each pair of points p and q in S, the graph G\E contains a path P between p and q with |P | ≤ t|P S | where P S is the shortest path between p and q in the graph K S \E in which that K S is Euclidean complete graph on S. Levcopoulos et al. [START_REF] Levcopoulos | Improved algorithms for constructing fault-tolerant spanners[END_REF] for the first time considered the problem of constructing fault-tolerant spanners in Euclidean spaces efficiently. They proposed three algorithms that construct k-vertex fault-tolerant spanners. Some other works on the fault tolerant spanners have been done [START_REF] Czumaj | Fault-tolerant geometric spanners[END_REF][START_REF] Lukovszki | New results on fault tolerant geometric spanners[END_REF].

In 2009, Abam et al. [START_REF] Abam | Region-fault tolerant geometric spanners[END_REF] introduced the concept of region-fault tolerant spanner for planar point sets. For a fault region F and a geometric graph G on a point set S, assume G F is the remaining graph after removing the vertices of G that lie inside F and all edges that intersect F . For a set F of regions in the plane, an F-fault tolerant t-spanner is a geometric graph G on S such that for any region F ∈ F, the graph G F is a t-spanner for G c (S) F , where G c (S) is the complete geometric graph on S. They showed for any set of n points in the plane and any family C of convex regions, one can construct a C-fault tolerant spanner of size O(n log n) in O(n log 2 n) time.

In 2013, Alamdari et al. [START_REF] Alamdari | Self-approaching graphs[END_REF] introduced the concept of self-approaching and increasing-chord graph drawings. The problem is that, we are given a graph and we need to check if the graph has an self-approaching or increasing-chord embedding in the Euclidean space.

A geometric graph is self-approaching, if for every pair s and t of vertices of the graph, there exists a self-approaching path from s to t, denoted by st-path. A path from s to t is a self-approaching path if for each q on the path, not only the vertices, but any place of the path, if a point p starts at s and moves toward q, it always get closer to q in its movement. Also, a graph G is called increasing-chord if, for each pair u and v of its vertices, there exists a path between u and v such that the path is self-approaching both from u to v and from v to u. Obviously, an increasing-chord graph is a self-approaching graph.

In the geometric context, the position of the vertices of the graph is fixed, so we just want to know whether a given geometric graph is self-approaching or increasing-chord. One of the interesting properties of these graph is the following. It is known that the stretch factor (or dilation) of any self-approaching graph is at most 5.3332 [START_REF] Icking | Self-approaching curves[END_REF] and the stretch factor of any increasing-chord graph is at most 2.094 [START_REF] Rote | Curves with increasing chords[END_REF].

Our results. In this paper, we prove the following results. For the rest of the paper S denotes a set of n points in the plane.

1. The continuous Yao graph cY (θ) on S is a C-fault-tolerant geometric tspanner of S, where 0 < θ < π/3 and t ≥ 1 1-2 sin(θ/2) . 2. For any θ ≤ π the graph cY (θ) h on S is connected, where h is an arbitrary half-plane in the plane. 3. There is a set of n points in the plane and a convex region C such that for every θ ≥ π 3 , cY (θ) C is not connected. 4. There is a set P of n points in the plane such that for some angles θ, Yao graph on P with parameter θ is not a self-approaching graph. Instead, the corresponding continuous Yao graph on P is a self-approaching graph. 5. For every θ > 0, cY (θ) is not necessarily a self-approaching graph.

cY (θ) is fault-tolerant

In this section, we show that the continuous Yao graph cY (θ) for 0 < θ < π/3 and t ≥ 1 1-2 sin(θ/2) is a C-fault-tolerant geometric t-spanner where C is the family of convex regions in the plane. Furthermore, we show that for every θ ≤ π and every half-plane h, cY (θ) h is connected. Moreover, we show that there is a set of n points such that for a some convex region C, cY (θ) C is not connected for every θ ≥ π 3 . We need the following lemmas. Let h be an arbitrary half-plane in H. We must show that for each pair of points p, q ∈ S outside h, there is a t-path between p and q in cY (θ) h. The proof is by induction on the rank of distance |pq|.

For the base step, suppose that the pair p and q is the closest pair in cY (θ) h. Without loss of generality, assume the distance between p and h is less than of equal to the distance between q and h. Since p and q are outside h and θ < π/2, there is a θ-cone C p with apex at p completely outside h such that q ∈ C p . Since pair p and q is the closest pair, by the construction of cY (θ), the edge (p, q) must be in cY (θ) h. Note that if both p and q have same distance to h, then we can choose both p and q as apex, but we have to choose the point such that the corresponding θ-cone does not intersect h.

For the induction hypothesis step, suppose for each pair u, v ∈ S outside h with |uv| < |pq| there is a t-path between u and v connecting them in cY (θ) h. Now we consider the induction step. Since p and q are outside h, there is a θ-cone C p with apex at p such that q ∈ C p (here we assumed that p is closer than q to h).

Suppose that r is the closest point to p inside the cone C p (see Fig. 1). Since θ < π/3, 1 -2 sin(θ/2) > 0, and also since |pr| ≤ |pq|, by Lemma 1 we have |rq| < |pq|. Therefore, by the induction hypothesis, there is a t-path Q between r and q in cY (θ) h. Now consider the path P := {(p, r)} ∪ Q. Clearly the path P connects p and q, and P is in cY (θ) h. Now by Lemma 1, we have

|P | = |pr| + |Q| ≤ |pr| + t|rq| ≤ |pr| + t (|pq| -(1 -2 sin(θ/2))|pr|) = t|pq| + (1 -t(1 -2 sin(θ/2))) |pr| ≤ t|pq| since t ≥ 1 1 -2 sin(θ/2)
.

Thus P is a t-path in cY (θ) h between p and q. This completes the proof. Note that even though cY (θ) is a C-fault tolerant spanner, it is not necessarily connected. It is because in fault-tolerant spanners, we compare the graph with the complete graph. So if the complete graph after removing points in some regions becomes disconnected, then some of fault-tolerant spanners of the points set might be disconnected. In the following, we show that for every half-plane h in the plane, the graph cY (θ) h is a connected graph for every θ ≤ π.

Lemma 3. The continuous Yao graph cY (π) on each set S contains CH(S), the convex hull of S.

Proof. Proof is straightforward.

Theorem 2. For any θ ≤ π the graph cY (θ) h on S is connected, where h is a half-plane.

Proof. It is easy to see that for every α, β > 0, if α ≥ β then cY (α) ⊆ cY (β). So, to prove the theorem, it is sufficient to show that cY (π) h is connected for every half-plane h.

Let h be an arbitrary half-plane in the plane. Suppose that cY (π) h is not connected.

Since cY (π) h is disconnected, it has more than one connected component. At least one of the connected components of cY (π) h contains a point from CH(S). Suppose C and C are two (distinct) connected components of cY (π) h such that at least one of them, say C, contains a point from CH(S). If both of C and C contains a point from CH(S) then by Lemma 3, part of CH(S) which lies outside h is connected which is a contradiction because we assumed that C and C are distinct connected components of cY (π) h. Now, assume C contains no vertices on CH(S). Let x be the intersection of boundary of h and CH(S) and let be a line through x and tangent to C (see Fig. 2). We have two cases. Case 1: ∩ C contains exactly one point denoted by y. If x ∈ S then clearly by the construction of graph cY (π), the vertex y should be connected to a vertex of C that is contradiction, since we assumed that C and C are distinct connected components of cY (π) h. Now, suppose that x ∈ S. Since ∩ C contains exactly one point, we can with continuously rotating the line around the point y (in Fig. 2, we rotate counter-clockwise), find a line such that ∩ C contains exactly one point that is y, and also the point in the intersection of and boundary h does not belong to S. Hence, by the construction of graph cY (π), point y should be connected to a vertex of C. That is a contradiction with that C and C are distinct connected components of cY (π) h.

Case 2: is tangent to C in at least two points. We claim that there is a line that is tangent to exactly one point of S on the convex hull of C (denoted by s). Suppose that s be the farthest point of S on with respect to x, and suppose that r be the next point after s on the convex hull of C in counterclockwise order (see Fig. 3). Let be a line that through of s and r, and let z be the intersection of and boundary of h. Now suppose that w be a point on the segment xz (w = x, z). Let be a line that through of w and s. Clearly is tangent to exactly one point of S that is s on the convex hull of C . Now by the construction of cY (π), vertex s should be connected to a vertex of connected component of C. This contradicts with the assumption that C and C are distinct connected components of cY (π) h.

According to the above mentioned cases, cY (π) h is connected. This completes the proof. In the following, we give an example such that for every θ ≥ π 3 , cY (θ) C for some convex region C is not necessarily connected.

Assume P 0 = (0, 0), (1, √ 3), (2, 0) which is the vertices of a equilateral triangle. Let P i be the translation of P 0 by value c × i horizontally where c is a sufficiently large constant positive integer. Here, we consider c = 10 (see Fig. 4). We choose the set P := k-1 i=0 P i . Let θ be an angle with θ ≥ π 3 . Consider cY (θ) on P . Note that for θ ≥ π 3 , cY (θ) on the vertices of an equilateral triangle is exactly the complete graph of their vertices. Now, let C be a convex region such that C only contains the points (1, √ 3), (2, 0), (10, 0) and (11, √ 3) from P (see Fig. 4). Since in the cY (θ) the vertex (0, 0) is only connected to the vertices (1, √ 3) and (2, 0), clearly in cY (θ) C there is no path between (0, 0) and [START_REF] Lukovszki | New results on geometric spanners and their applications[END_REF]0). Hence cY (θ) C is not connected.

P 0 P 1 P k-1 C (1, √ 3) (11, √ 3) (0, 0) (2, 0) (10, 0) (12, 0)
Fig. 4. An example that cY (θ) is disconnected after convex region fault.

cY (θ) is not self-approaching

In this section, we show that there is a set P of n points in the plane such that for some angles θ, Yao graph on P with parameter θ is not a self-approaching graph. Instead, the corresponding continuous Yao graph on P is a self-approaching graph. Finally, we show that there is a set of n points in the plane such that for every θ > 0, continuous Yao graph cY (θ) is not a self-approaching graph.

In the following, we assume that the number of cones is even. With making some modifications, similar results holds for odd number of cones. Now, let p = (0, 0), q = (1, 0), r = (r 1 , r 2 ) and s = (s 1 , s 2 ) be four points in the plane. For three points x, y and z, let ∠yxz be the angle between the segment xy and xz. Now, assume that ∠qpr = α 1 , ∠pqr = α 2 , ∠prq = α 3 , ∠qps = β 1 , ∠pqs = β 2 , ∠psq = β 3 , for some angles α i and β i with 0 < α i < π/2 and 0 < β i < π/2 for i = 1, 2, 3 (see Fig. 5).

We call the quadrilateral on the four points p, q, r and s a bad quadrilateral if we have the following properties: 5. A bad quadrilateral on the points p, q, r and s. Now, we consider k cones, generated by the k-rays through origin, where the ith ray has angle (i -1)θ with the positive x-axis. The ith cones contains the points p such that the angle of line op with positive x-axis is bigger than or equal (i -1)θ and less than iθ.

1. |pq| cos α 1 < |pr| < |pq| 2. |pq| cos α 2 < |qr| < |pq| 3. |pq| cos β 1 < |ps| < |pq| 4. |pq| cos β 2 < |qs| < |pq| p q α 1 α 2 α 3 β 2 β 1 β 3 r s Fig.
Let V be a set of four points p = (0, 0), q = (1, 0), r = (r 1 , r 2 ) and s = (s 1 , s 2 ) such that the quadrilateral on the vertices p, q, r and s is a bad quadrilateral. It is easy to see that, for every θ with α 1 < θ ≤ π 2 such that 2π θ is even number and β 2 < θ, the Yao graph Y k on V where k = 2π θ does not contain the edge {p, q} but it contains the edges {p, r}, {p, s}, {q, r} and {q, s}. So the Yao graph Y k on the point set V is not a self-approaching graph, since every path from p to q is not a pq-path. Indeed, the following lemma shows that cY (θ) on V is a self-approaching graph.

Lemma 4. Let α 1 + β 1 ≥ π 2 or α 2 + β 2 ≥ π 2 .
For every θ such that a) α 1 < θ ≤ π 2 , and b) θ < α 1 + β 1 or θ < α 2 + β 2 , and c) 2π

θ is even number, and d) β 2 < θ, continuous Yao graph cY (θ) on V contains the edge {p, q}. Furthermore, cY (θ) on V is a self-approaching graph.

Proof. We prove the theorem for the case that θ < α 1 + β 1 . Similar argument works for the case θ < α 2 + β 2 .

Since θ < α 1 + β 1 , by construction of cY (θ), clearly there is a θ-cone C with apex p that only contains the point q. Hence the edge {p, q} is in cY (θ).

On the other hand, the Yao graph on V with angle parameter θ is a subgraph of cY (θ), so the edges {p, r}, {p, s}, {q, r} and {q, s} are in cY (θ). So, we only need to show that there is a self-approaching path from r to s and a self-approaching path from s to r.

Since

α 1 + β 1 ≥ π 2 or α 2 + β 2 ≥ π 2
, the path r → q → s or r → p → s is an rs-path and in the reverse direction is an sr-path. So there is an xy-path between all ordered pairs {x, y} for x, y ∈ V . Hence, cY (θ) is a self-approaching graph on V . This completes the proof.

Next, we will give another point set such that the Yao graph on the point set is not self-approaching graph, but the continuous Yao graph is a self-approaching graph.

Let P be a set of n points as follows:

P = V ∪ {x 1 , x 2 , . . . , x n-4 }, (1)
with x j = (c + j, 0) for 1 ≤ j ≤ n -4 where c is a sufficiently large constant positive integer. Here, we consider c = 19 (see Fig. 6). Now, using Lemma 4 we can easily find the following result.

Lemma 5. Let α 1 + β 1 ≥ π 2 or α 2 + β 2 ≥ π 2 . For every θ such that a) α 1 < θ ≤ π 2 , and b) θ < α 1 + β 1 or θ < α 2 + β 2 ,

and c) 2π

θ is even number, and d) β 2 < θ, continuous Yao graph cY (θ) on P is self-approaching and Y k is not a selfapproaching for k = 2π θ .

p q r r x 1 x 2 x 3 x 4
Fig. 6. The set P with n = 8.

Note that there are some point set that satisfy the conditions mentioned in above lemmas. For example, let V = {p, q, r, s} with p = (0, 0), q = (1, 0), r = (0.7839, 0.4422), s = (0.2161, -0.4422), and suppose that k = 4 and θ = π 2 . We can easily verify that the quadrilateral on the points of V is a bad quadrilateral. Moreover we have

α 1 = 29.4271 • , α 2 = 63.9535 • , α 3 = 86.6198 • , β 1 = 29.4271 • , β 2 = 63.9535 • , β 3 = 86.6198 • .
Now, suppose that P = V ∪ {x 1 , x 2 , . . . , x n-4 } where x i = (19 + i, 0). This point set satisfies Lemma 5.

At the first view, it seems that the continuous Yao graph is a self-approaching graph, but this is not true in general. Next, we give a point set such that for each θ, the continuous Yao graph cY (θ) on the point set is not a self-approaching graph.

Theorem 3. There is a set P of n points such that for every θ > 0, cY (θ) on P is not a self-approaching graph.

Proof. We prove the theorem for 0 < θ ≤ 2π 3 . Since for every α 1 and α 2 with α 1 ≤ α 2 we have cY (α 2 ) ⊆ cY (α 1 ), the theorem holds for every θ > 0.

Consider two points p = (0, 0) and q = (1, 0). Let C be a circle centered at the midpoint of the segment pq, with radius 1 2 . Let D p and D q be circles respectively centered at p and q with radius one. Let be the perpendicular bisector of segment pq (see Fig. 7).

Consider x and y as points outside C and inside D p ∩ D q such that ∠xpq < θ 2 and ∠ypq < θ 2 . Let x and y be the symmetries of x and y with respect to line , respectively. Now let V = {p, q, x, y, x , y }, and consider cY (θ) on V . Since ∠xpy = ∠x qy < θ, cY (θ) does not contain the edge {p, q}. So, by our selection of points x, y, x and y , there is no self-approach path between p and q. Hence, cY (θ) on V is not self-approaching.

One can extend this point set to a point set with arbitrary number of points such that cY (θ) is not a self-approaching graph of the point set. To this end, one can add any point to V which is sufficiently far from the points in the original set V , because adding points which are far can not help in making a self-approaching path from p to q.

Concluding remarks

We proved that for 0 < θ < π/3 and t ≥ 1 1-2 sin(θ/2) , the continuous Yao graph cY (θ) is a C-fault-tolerant geometric t-spanner. Furthermore, we showed that for every θ ≤ π and every half-plane h, cY (θ) h is connected. Finally, we showed that for every θ > 0, cY (θ) is not necessarily a self-approaching graph. The question whether cY (θ) for π 3 ≤ θ ≤ π is a C-fault-tolerant geometric spanner with constant stretch factor remains open.

Fig. 1 .

 1 Fig. 1. Illustrating of the proof of Theorem 1.

Fig. 2 .

 2 Fig. 2. Illustrating of the proof of Theorem 2: case 1.

Fig. 3 .

 3 Fig. 3. Illustrating of the proof of Theorem 2: case 2.

Fig. 7 .

 7 Fig. 7. Illustrating of the proof of Theorem 3.

  Lemma 1 ([4]). Let a, b and c be three points such that |ac| ≤ |ab| and ∠bac ≤ α < π. Then |bc| ≤ |ab| -(1 -2sin(α/2))|ac|. Lemma 2 ([1]). A geometric graph G on S is a C-fault tolerant t-spanner if and only if it is an H-fault-tolerant t-spanner, where H is the family of all halfplanes. . For any point set S, the continuous Yao graph cY (θ) is a C-fault-tolerant geometric t-spanner. Proof. By Lemma 2, it is sufficient to prove that cY (θ) is an H-fault-tolerant geometric t-spanner.

	Now, we prove the following theorem:
	Theorem 1. Let θ be a real number with 0 < θ < π/3 and let t be a real number
	with t ≥	1 1-2 sin(θ/2)


Prosenjit Ahmad Biniaz

Anil Bose

Michiel Maheshwari

Smid

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

Let S be a finite set of points in the interior of a simple polygon P . A geodesic graph, GP (S, E), is a graph with vertex set S and edge set E such that each edge (a, b) ∈ E is the shortest path between a and b inside P . GP is said to be plane if the edges in E do not cross. If the points in S are colored, then GP is said to be properly colored provided that, for each edge (a, b) ∈ 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.

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 π(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) ∈ E is the geodesic π(a, b) in P . If P is a convex polygon, then G P is a straight-line geometric graph.

Let π 1 and π 2 be two, possibly self-intersecting, curves. We say that π 1 and π 2 cross if by traversing π 1 from one of its endpoints to the other endpoint we encounter a neighborhood of π 1 where π 2 intersects π 1 and switches from one side of π 1 to the other side [START_REF] Toussaint | Computing geodesic properties inside a simple polygon[END_REF]. We say that π 1 and π 2 are non-crossing if they do not cross. Two non-crossing curves can share an endpoint and can "touch" each other. If π 1 and π 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) ∈ 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 , . . . , S k }, where k ≥ 2, be a partition of S. Let K P (S 1 , . . . , 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 ≤ i < j ≤ k. Imagine the points Research supported by NSERC. in S to be colored, such that all the points in S i have the same color, and for i = 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 , . . . , 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 , . . . , 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 , . . . , 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 , . . . , S k ). A t-tree is a tree of maximum degree t. See Figure 2.

Preliminaries

We say that a set S of points in the pale 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, π(a, b) does not contain any point of S \ {a, b}.

Toussaint [START_REF] Toussaint | Computing geodesic properties inside a simple polygon[END_REF] 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 , . . . , p m ), possibly with repeated vertices, such that every pair of distinct vertices of P partitions P into two non-crossing polygonal chains [START_REF] Toussaint | Computing geodesic properties inside a simple polygon[END_REF]. 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 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 n/2 , 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 n/2 . Assume S is color-balanced and is in the interior of a simple polygon P . Let π be a geodesic in P . Let P 1 and P 2 be the (weakly) simple polygons on each side of the extended geodesic π. Let T 1 and T 2 be the points of S in P 1 and P 2 , respectively. We say that π 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 2n 3 + 1. See Figure 3. The ham-sandwich geodesic (see [START_REF] Bose | Geodesic ham-sandwich cuts[END_REF]) 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 π be a ham-sandwich geodesic for R and Bose et al. [START_REF] Bose | Geodesic ham-sandwich cuts[END_REF] 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.

B in P . If R ∪ B ∪ F is in general position, then

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 R 2 \ 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 , . . . , S k }, where k ≥ 2, and the points in S i are colored C i . Let K(S 1 , . . . , S k ) be the complete straight-line multipartite geometric graph on S. Observe that if K(S 1 , . . . , 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 , . . . , S k ). See [START_REF] Abellanas | Bipartite embeddings of trees in the plane[END_REF][START_REF] Kaneko | Discrete geometry on red and blue points in the plane-a survey[END_REF] for examples. Kaneko [START_REF] Kaneko | On the maximum degree of bipartite embeddings of trees in the plane[END_REF] 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. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF] extended this result for k ≥ 2: if S is weakly color-balanced, then K(S 1 , . . . , 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 , . . . , S k ) follows from a result of Sitton [START_REF] Sitton | Maximum matchings in complete multipartite graphs[END_REF].

Corollary 1. Let {S 1 , . . . , S k } be a partition of a point set S in the plane, where k ≥ 2 and |S| is even. Then, K(S 1 , . . . , S k ) has a colored matching if and only if S is color-balanced.

Aichholzer et al. [START_REF] Aichholzer | Edge-removal and non-crossing configurations in geometric graphs[END_REF], and Kano et al. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF] 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 , . . . , S k ):

Theorem 1 (Aichholzer et al. [START_REF] Aichholzer | Edge-removal and non-crossing configurations in geometric graphs[END_REF], and Kano et al. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF]). Let {S 1 , . . . , S k } be a partition of a point set S in the plane, where k ≥ 2 and |S| is even. Then, K(S 1 , . . . , S k ) has a plane colored matching if and only if S is color-balanced.

In fact, they show something stronger. Aichholzer et al. [START_REF] Aichholzer | Edge-removal and non-crossing configurations in geometric graphs[END_REF] showed that any minimum-weight colored matching in K(S 1 , . . . , S k ), which minimizes the total Euclidean length of the edges, is plane. Kano et al. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF] presented a constructive proof for the existence of a plane colored matching in K(S 1 , . . . , S k ). Biniaz et al. [START_REF] Biniaz | An optimal algorithm for plane matchings in multipartite geometric graphs[END_REF] presented an algorithm which computes a plane colored matching in Although any minimum-weight colored matching in K(S 1 , . . . , S k ) is noncrossing, this is not always the case for any minimum-weight colored geodesic matching in K P (S 1 , . . . , 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.

K(S 1 , . . . , S k ) optimally in Θ(n log n) time. (a) (b) (c) (d)
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 noncrossing 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.

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 , . . . , S k }, where k ≥ 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 = 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. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF] for geodesic 3-trees. We show that if S is weakly color-balanced and S ∪ F is in general position, then K P (S 1 , . . . , 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 ∪ 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 , . . . , S k ) in O(nm log m + n log n log m) time by recursively finding balanced geodesics.

Plane Geodesic Hamiltonian Cycles

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 "counterclockwise" 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 ∪ {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 -→ π (s, t). The algorithm stops as soon as t reaches its initial position, i.e., s. For two points a, b ∈ S we say that a ≺ b if -→ π (s, t) meets a before b. Thus, the sweep-path algorithm defines a total ordering S = (s 1 , . . . , s n ) on the points in S such that s i ≺ s j , for all 1 ≤ i < j ≤ 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 ∪{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 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 -→ π (s, p) is a(R). Moreover, all points of R have the same internal vertex sequence in their shortest path to s.

s t a(R) R s R2 R3 R4 R5 R7 R9 R13 R14 R15 R1 R6 R10 R11 R12 R8 v v 1 v 2 (a) (b)
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 ∈ 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 R = (R 1 , R 2 , . . . ) 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 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. [START_REF] Guibas | Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons[END_REF]. A planar point location data structure for SPM(s) can be constructed in O(m) time and answers point location queries in O(log m) time [START_REF] Kirkpatrick | Optimal search in planar subdivisions[END_REF]. 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) [START_REF] Guibas | Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons[END_REF]. 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)). R 8 R 11 R 12 R 14 R 15 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 9 R 10 R 13 s R 3 R 7 R 1 v v 1 v 2 v v 1 v 2 P (v)
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.

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

Lemma 1. Let S = (s 1 , . . . , 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 ≤ i < j ≤ k < l ≤ n. Then, π(s i , s j ) and π(s k , s l ) are non-crossing.

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 ⊆ P is called geodesically (or relative) convex if for any pair of points a, b ∈ 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 [START_REF] Toussaint | Computing geodesic properties inside a simple polygon[END_REF] 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, π(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 \ {s 0 } in GH(S). It gives an ordering S = (s 1 , . . . , s n-1 ) for the points in S \ {s 0 }. We compute the following geodesic Hamiltonian cycle C (see Figure 7),

C = {(s i , s i+1 ) : 1 ≤ i ≤ n -2} ∪ {(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 ≤ i ≤ n -2. In addition, by Lemma 1 for 1 ≤ i < j ≤ k < l ≤ 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.

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 , . . . , 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 ≥ 4, then by using the technique in the proof of Lemma 2 in [START_REF] Biniaz | An optimal algorithm for plane matchings in multipartite geometric graphs[END_REF], 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. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF] 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. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF]). Let (s 1 , . . . , s n ) be a sequence of n ≥ 3 points colored with at most 3 colors 1 such that s 1 and s n have the same color. If {s 1 , . . . , s n } is weakly color-balanced, then there exists an even number p, 2 ≤ p ≤ n -1, such that both {s 1 , . . . , s p } and {s p+1 , . . . , s n } are weakly color-balanced.

Theorem 3 (Kano et al. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF]). 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 ≤ |R| ≤ 3, and s ∈ R, (ii) 2 ≤ |B|, |R| = |B| + 2, and s ∈ R, (iii) 2 ≤ |B| ≤ |R| ≤ |B| + 1.
Theorem 4 (Kano et al. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF]). 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.

1 Actually, they prove the statement of the theorem for 2-and 3-colored point sets.

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 [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF] 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 ≤ |R| ≤ 3, and s ∈ R, (ii) 2 ≤ |B|, |R| = |B| + 2, and s ∈ R, (iii) 2 ≤ |B| ≤ |R| ≤ |B| + 1.
Proof. The proof is by construction. Since for any two points a and b in S, π(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 \{s} which is rooted at x. Observe that x is a vertex of GH(S \ {s}) and π(s, x) does not intersect GH(S \ {s}). Then, T = T 1 + π(s, x) is the desired tree. If s, x, and y have the same color, then let S = (s 1 , . . . , s n-1 ), where s 1 = x and s n-1 = y, be the ordering of the points in S \{s} obtained by the sweep-path algorithm around s. See Figure 8(a). If s ∈ B, then let S = (s 1 , . . . , s n ), where s 1 = s, s 2 = x, and s n = y. See Figure 8(b). In either case-s ∈ R or s ∈ 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 π(s, s p ) (not including s and s p ), then both S 1 ∪ {s p } and S 2 are weakly color-balanced. Moreover, each of S 1 ∪ {s p } and S 2 ∪ {s p } satisfies one of the conditions (i), (ii), or (iii). Observe that π(s, s p ) does not cross any of GH(S 1 ∪ {s p }) and GH(S 2 ∪ {s p }). In addition, s p is a vertex of both GH(S 1 ∪ {s p }) and GH(S 2 ∪ {s p }). Let T 1 (resp. T 2 ) be the tree obtained recursively on S 1 ∪ {s p } (resp. S 2 ∪ {s p }) which is rooted at s p . Since d T1 (s p ) = 1 and d T2 (s p ) = 1, T = T 1 + T 2 + π(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)). 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| ≤ |G| ≤ |R|. The proof is by construction. If |R| = |S|/2 , we assume that G and B have the same color and solve the problem by Theorem 5. Assume that |R| ≤ |S|/2 -1. Observe that in this case S \ {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 \{s} which is rooted at x. Observe that x is a vertex of GH(S \ {s}) and x) does not intersect GH(S \ {s}). Then, T = T 1 + π(s, x) is the desired tree.

If s, x, and y have the same color, then let S = (s 1 , . . . , s n-1 ), where s 1 = x and s n-1 = y, be the ordering of points in S \ {s} obtained by the sweeppath 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 π(s, s p ), then both S 1 ∪ {s p } and S 2 are weakly color-balanced. Since |R| ≤ |S|/2 -1, S 2 ∪ {s p } is also color-balanced. Moreover, π(s, s p ) does not cross any of GH(S 1 ∪ {s p }) and GH(S 2 ∪ {s p }). Let T 1 (resp. T 2 ) be the tree obtained recursively on S 1 ∪ {s p } (resp. S 2 ∪ {s p }) which is rooted at s p . Since d T1 (s p ) = 1 and d T2 (s p ) = 1, T = T 1 + T 2 + π(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)).

Balanced Geodesics

Let S be set of n ≥ 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 , . . . , 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 |} ≤ 2n 3 + 1. We prove that if S ∪ 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 [START_REF] Biniaz | An optimal algorithm for plane matchings in multipartite geometric graphs[END_REF]. If k ≥ 4, then by using the technique in the proof of Lemma 2 in [START_REF] Biniaz | An optimal algorithm for plane matchings in multipartite geometric graphs[END_REF], 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. 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 ≤ |B| ≤ |G| ≤ |R|. Since P is color-balanced, |R| ≤ n 2 . Let X be an arbitrary subset of B such that |X| = |R| -|G|; note that X = ∅ when |R| = |G|, and |X| = |B| when |R| = n 2 (when n is even). Let Y = B -X. Let π be a ham-sandwich geodesic for R and G ∪ X in P (by imagining that the points in G ∪ X have the same color). Let T 1 and T 2 denote the set of points of S on each side of π; see Figure 9(a). Let R 1 , G 1 , and B 1 (= X 1 ∪ Y 1 ) be the set of red, green, and blue points in T 1 such that X 1 = X ∩ T 1 and Y 1 = Y ∩ 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 π does not contain any point of R ∪ G ∪ X. If π contains any point y ∈ Y , then by Observation 2, y is on an external segment of π. 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 π contains a point x ∈ R and a point y ∈ G ∪ X; see Figure 9(b). By Observation 2, x and y are on different external segments of π (unless π is a straight line segment). In this case, without loss of generality, assume |B 2 | ≥ |B 1 |. We adjust the external segments of π slightly such that x and y lie on the same side as T 2 , i.e., T 2 = T 2 ∪ {x, y} (if π is a straight-line segment, then we move π slightly such that T 2 = T 2 ∪{x, y}); see Figure 9(b). We prove that π satisfies the statement of the theorem. In either case we have

|R 1 | = |R|/2 , |R 2 | = |R|/2 , |G 1 | + |X 1 | = |R 1 |, and |G 2 | + |X 2 | = |R 2 |. Therefore, |T 1 | ≥ |R 1 | + |G 1 | + |X 1 | = 2 |R|/2 , |T 2 | ≥ |R 2 | + |G 2 | + |X 2 | = 2 |R|/2 . ( 1
= |R 1 ∪ G 1 | and t 2 = |R 2 ∪ G 2 |. Then, |T 1 | = t 1 + |B 1 | and |T 2 | = t 2 + |B 2 |. (2)
In addition,

t 1 = |R 1 | + |G 1 | = |R 1 | + (|R 1 | -|X 1 |) ≥ 2|R 1 | -|X| = 2 |R|/2 -(|R| -|G|) = |G| if R is even |G| -1 if R is odd, t 2 = |R 2 | + |G 2 | = |R 2 | + (|R 2 -|X 2 |) ≥ 2|R 2 | -|X| = 2 |R|/2 -(|R| -|G|) = |G| if R is even |G| + 1 if R is odd. ( 3
|, |T 2 |} ≤ n -2 |R| 2 ≤ n -2( |R| -1 2 ) ≤ n -|R| + 1. Since R is the largest color class, |R| ≥ n 3 . Therefore, max{|T 1 |, |T 2 |} ≤ n -n 3 + 1 = 2n 3 + 1.
The ham-sandwich geodesic π for R and G ∪ X in P can be computed in O((n+m) log m) time. Adjusting the external segments of π 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.

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 , . . . , S k }, where k ≥ 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 ∪ F is in general position, then K P (S 1 , . . . , S k ) contains a plane colored geodesic matching. In fact we show how to compute such a matching. If k ≥ 4, by the technique of Lemma 2 in [START_REF] Biniaz | An optimal algorithm for plane matchings in multipartite geometric graphs[END_REF], 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. [START_REF] Kano | Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane[END_REF]-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 π 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 colorbalanced with an even number of points, and max{|T 1 |, |T 2 |} ≤ 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 π, M 1 ∪ 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 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 ∪ 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 [START_REF] Aichholzer | Geodesicpreserving polygon simplification[END_REF], 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(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)polylog(nm)).

Fig. 1 .

 1 Fig. 1. (a) Two crossing geodesics, and (b) two non-crossing geodesics.

Fig. 2 .

 2 Fig. 2. (a) A plane colored geodesic matching, and (b) a plane colored geodesic 3-tree.

Fig. 3 .

 3 Fig. 3. A color-balanced point set S in the interior of a simple polygon P . (a) A balanced geodesic π(a, b) with external vertices a and b. (b) The extended geodesic π(a, b) divides P into P1, P2, and partitions S into T1, T2.

Fig. 4 .

 4 Fig. 4. (a) A minimum-weight colored geodesic matching which is crossing. (b) A noncrossing matching in the plane, and (c) its geodesic mapping which is crossing. (d) A non-crossing geodesic matching.

Fig. 5 .

 5 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).

Fig. 7 .

 7 Fig. 7. (a) Points of S which are sorted by the sweep-path algorithm. (b) A plane geodesic Hamiltonian cycle (assuming s0 is a point of S).

Fig. 8 .

 8 Fig. 8. Illustration of Theorem 5: (a) |R| = |B| + 2, s ∈ R, and (b) |R| = |B| + 1, s ∈ B.

Theorem 7 (

 7 Balanced Geodesic Theorem). Let S be a color-balanced point set of n ≥ 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 ∪ F is in general position, then in O((n + m) log m) time we can compute a geodesic π such that 1. π does not contain any point of S. 2. π 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 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 , . . . , 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 ≥ 4.Ifk = 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 π be a ham-sandwich geodesic of S in P . By Observation 2, if |S 1 | and |S 2 | are even numbers then π 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 π contains a red point, say r, and the other external segment contains a blue point, say b. We adjust the external segments of π (by slightly moving its external vertices on P ) such that both r and b lie on the same side of π. If π is a straight line segment, then we move π slightly such that both r and b lie on the same side of π. In either case, π is a desired balanced geodesic.

Fig. 9 .

 9 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 π, with endpoints p and q, is a balanced geodesic when: (a) |R| is even, and (b) |R| is odd.

  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 π 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 | ≤ 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).

  • the internal segments of π do not contain any point of R ∪ B. • if |R| (resp. |B|) is an even number, then the external segments of π 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 π contains exactly one point of R (resp. B). Moreover, if both |R| and |B| are odd numbers, then the two points which are on π, belong to different external segments of π (assuming π is not a straight-line segment).

)

  By the ham-sandwich geodesic we have|G 1 | ≤ |R 1 |. This and Inequality (1) imply that |G 1 | ≤ |R 1 | = |R|/2 ≤ |T 1 |/2. Similarly, we have |G 2 | ≤ |R 2 | = |R|/2 ≤ |T 2 |/2.In order to prove that T 1 and T 2 are color-balanced, we have to show that|B 1 | ≤ |T 1 |/2 and |B 2 | ≤ |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

)

  Recall that |B| ≤ |G|. Equation[START_REF] Aichholzer | Edge-removal and non-crossing configurations in geometric graphs[END_REF] and Inequality[START_REF] Aichholzer | Geodesicpreserving polygon simplification[END_REF] imply that |B 2 | ≤ |T 2 |/2. If |R| is an even number, then Equation (2) and Inequality (3) imply that |B 1 | ≤ |T 1 |/2. If |R| is an odd number, then by assumption we have |B 1 | ≤ |B 2 |; this implies that |B 1 | ≤ |B| -1. Again by Equation (2) and Inequality (3) we have |B 1 | ≤ |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 |R|/2 . This implies that, max{|T 1