Printer Friendly

A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon.

We present a randomized algorithm to compute a clique of maximum size in the visibility graph G of the vertices of a simple polygon P. The input of the problem consists of the visibility graph G, a Hamiltonian cycle describing the boundary of P, and a parameter [delta] [member of] (0,1) controlling the probability of error of the algorithm. The algorithm does not require the coordinates of the vertices of P. With probability at least 1-[delta] the algorithm runs in O [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] time and returns a maximum clique, where [omega](G) is the number of vertices in a maximum clique in G. A deterministic variant of the algorithm takes O(|E[(G)|.sup.2]) time and always outputs a maximum size clique. This compares well to the best previous algorithm by Ghosh et al. (2007) for the problem, which is deterministic and runs in O (|V [(G) |.sup.2] |E (G)|) time.

Keywords: visibility graph, maximum clique, simple polygon, randomized algorithm

1 Introduction

A (simple) polygon is the region of the plane bounded by a non-self-intersecting, closed, polygonal path. The polygonal path itself is part of the polygon; it is usually called its boundary. A polygon P defines a (vertex) visibility graph G = G(P) in a natural way. The vertices of G are the vertices of the polygon. There is an edge between two vertices v and v' of G whenever the edge segment connecting v and v' is contained in P. In particular, the edges of the polygon correspond to edges of the visibility graph G. In fact, the edges of the polygon define a Hamiltonian cycle in G.

Several optimization problems have been considered for geometrically constrained graphs. In this paper, we are interested in finding a maximum clique in the visibility graph of a polygon. A clique is a complete subgraph. Thus, a clique in a graph H contains a subset of the vertices of H with the property that each two vertices are connected by an edge. The clique number of H, usually denoted by [omega](H), is the number of vertices in a maximum clique.

A clique in the visibility graph of a polygon has a simple, nice geometric interpretation. A subset of the vertices of P forms a clique whenever they are pairwise visible. It is possible to see that the vertices of a clique of the visibility graph G are in convex position. In fact, the vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of P, enumerated as they appear along the boundary of P, form a clique if and only if the polygonal path Q defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] forms a convex polygon contained in P. In particular, the edges of Q have to be edges of G.

The visibility graph G of a polygon P can be computed efficiently in O(|E(G)|) time using the algorithm of Hershberger [Her89] together with linear-time triangulation [Cha91]. See the algorithm by Ghosh and Mount [GM91] for polygons with holes. However, the inverse direction is unclear: given a graph G, it is not known how to decide whether this is the visibility graph of a polygon. In particular, we cannot reconstruct efficiently a polygon whose visibility graph is given. See the discussion by Ghosh and Goswami [GG13, Gho07, Gho97].

We consider the following restricted scenario: the geometric coordinates of the polygon P are unknown. The information available as input is the visibility graph G and a Hamiltonian cycle C describing the boundary of P. As discussed before, with our current knowledge this information is strictly weaker than having the coordinates describing P. The objective is to find a maximum clique in G. The very same model and problem is considered by Ghosh, Shermer, Bhattacharya, and Goswami in [GSBG07] (see alternatively [Gho07, Section 6.7]), where an algorithm with time complexity O(|V[(G)|.sup.2] |E(G)|) is given. Using a modification of the ideas of Fisher [Fis97], Avis and Rappaport [AR85], or Bautista-Santiago et al. [BSDBL+11], if the coordinates of the vertices are available we can obtain a better algorithm running in O(|V(G)| |E(G)|) time.

For the aforementioned restricted scenario, we provide a deterministic algorithm finding a maximum clique in O(|E[(G)|.sup.2]) time, and a randomized algorithm finding a maximum clique in O [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] time with probability at least 1 - [delta]. At a very high-level, our approach is an adaptation of the dynamic programming of Fisher [Fis97] and Bautista-Santiago et al. [BSDBL+11] that infers enough information from the cycle C and the visibility graph G.

Our algorithms compare favorably with the result of Ghosh et al [GSBG07]: The deterministic algorithm is faster than the algorithm in [GSBG07] when G is sparse, i.e. when |E(G) | = o(|V[(G)|.sup.2]); otherwise, the two algorithms have the same asymptotic running time. On the other hand, for constant values of [delta] the randomized algorithm is faster than the algorithm in [GSBG07] when |E(G)| = o(|V[(G)|.sup.2]), and when |E(G)| = [THETA](|V[(G)|.sup.2]) and [omega](G) is super-constant. There exist situations where |E(G)| = [THETA](|V[(G)|.sup.2]) and the size of [omega](G) is constant (see, for example, Figure 1), in which case the randomized algorithm does not give a speed-up.

We next introduce some notation. In Section 2 we provide geometric lemmas to extract certain geometric information from G and C. The description of the algorithm is in Section 3.

Notation. We assume that P has n vertices. Let C = [v.sub.1][v.sub.2] ... [v.sub.n][v.sub.1] be the Hamiltonian cycle describing the boundary of P. Throughout the paper, indices of vertices are treated modulo n, sothat[v.sub.n+i] = [v.sub.i]. With a slight abuse of notation, we use [v.sub.i] to refer to both the vertex of the polygon P and the corresponding vertex in the visibility graph G.

In our drawings we will assume that C gives the vertices in counterclockwise order; however, the algorithm is oblivious to the orientation.

[FIGURE 1 OMITTED]

For any two vertices [v.sub.i] and [v.sub.j] of G, let C([v.sub.i], [v.sub.j]) be the set of vertices in C as we walk from [v.sub.i] to [v.sub.j] along C, without [v.sub.i] and [v.sub.j]. For example, C([v.sub.i], [v.sub.i+1]) = [??] and C([v.sub.i], [v.sub.i+2]) = {[v.sub.i+1]}. Similarly as it is done for intervals, let C([v.sub.i], [v.sub.j]] = C([v.sub.i], [v.sub.j]) [union] {[v.sub.j]}.

For each vertex v, deg(v) is the number of neighbours of v in G. It holds that [[summation].sub.v[member of]V(G)] deg(v) = 2 * |E(G)|.

2 Geometric preliminaries

In this section we prove some geometric lemmas needed to argue the correctness of our algorithm. Some of these results are implicit in [GSBG07].

Lemma 1 Let vi be a vertex of G and let [U.sub.i] be the set of vertices visible from [v.sub.i]. The order of the vertices of [U.sub.i] along C is the same as the (clockwise or counterclockwise) order of the edges {[v.sub.i]u | u [member of] [U.sub.i]} around [v.sub.i].

Proof: Assume that C gives the counterclockwise ordering along the boundary of P; the clockwise ordering is similar. Consider any two edges [v.sub.i]u and [v.sub.i]u' with u, u' [member of] [U.sub.i]. Assume that u' [member of] C(u, [v.sub.i]) (see Figure 2). Then [v.sub.i]u' lies counterclockwise between [v.sub.i]u and [v.sub.i][v.sub.i-1]. Indeed, the diagonal [v.sub.i]u cuts the polygon P into two polygons P' and P". Let P' be the polygon defined by C(u, [v.sub.i]), [v.sub.i] and u. The vertex u' belongs to P'. This means that [v.sub.i]u' is a diagonal of P' and it lies counterclockwise between [v.sub.i]u and [v.sub.i][v.sub.i-1].

Let [K.sub.t] be a clique in G. A consequence of the previous lemma is that the order of the vertices of [K.sub.t] along the convex hull of V([K.sub.t]) is the same as the order along the boundary of P. Indeed, the circular ordering along the convex hull of V([K.sub.t]) is the same as the circular ordering of the edges of E([K.sub.t]) from any vertex of V([K.sub.t]).

Let Q be a simple polygon, and let [u.sub.1][u.sub.2] ... [u.sub.m][u.sub.1] be the Hamiltonian cycle describing its boundary. We say that vertex [u.sub.i] is convex if the interior angle of Q defined by edges [u.sub.i-1][u.sub.i] and [u.sub.i][u.sub.i+1] is convex. Notice that Q is a convex polygon if and only if all its vertices are convex.

The following lemma gives a tool to extend cliques. See Figure 3, left, for an illustration.

Lemma 2 Let [v.sub.1], [v.sub.l], [v.sub.i], [v.sub.n] be distinct vertices of V(G) with [v.sub.l] [member of] C([v.sub.1],[v.sub.i]). Let U be a subset of vertices from C([v.sub.1], [v.sub.i]) such that U [union] {[v.sub.1], [v.sub.l], [v.sub.i], [v.sub.n]} is a clique in G. Possibly U is empty. Let [v.sub.j] [member of] C([v.sub.i], [v.sub.n]). If [v.sub.j] sees [v.sub.1], [v.sub.l], [v.sub.i], [v.sub.n], then U [union] {[v.sub.1], [v.sub.l], [v.sub.i], [v.sub.j], [v.sub.n]} is a clique in G.

[FIGURE 2 OMITTED]

Proof: Consider the closed polygonal curve Q that follows the vertices of U, in the same order as they appear along C([v.sub.1], [v.sub.l]), followed by [v.sub.l], [v.sub.i], [v.sub.j], [v.sub.n], [v.sub.1]. Since all vertices of Q are visible from [v.sub.1] and have increasing indices, the path Q does not self-intersect. Thus Q is a polygon. Since Q is made of edges from E(G), it is contained in P. All the vertices of Q, but those at [v.sub.i], [v.sub.j], [v.sub.n], are convex because U [union] {[v.sub.1],[v.sub.l], [v.sub.i], [v.sub.n]} is a clique. The vertices [v.sub.i], [v.sub.j], [v.sub.n] of Q are convex because the edges [v.sub.l][v.sub.j], [v.sub.i][v.sub.n], [v.sub.j][v.sub.1] are in E(G), respectively.

[FIGURE 3 OMITTED]

The following lemma shows that, in a certain configuration, the vertices visible from [v.sub.j] have a very precise structure determined by a single index. See Figure 3, right, for an illustration.

Lemma 3 Let [v.sub.1][v.sub.i][v.sub.n] be a triangle in G and let U be the set of vertices visible simultaneously from [v.sub.1], [v.sub.i] and [v.sub.n]. Let [v.sub.j] be a vertex from U [intersection] C([v.sub.i],[v.sub.n]). There exists some index m[j] [member of] (1, i) such that U [intersection] C([v.sub.1], [v.sub.m[j]]] = {[v.sub.l] | [v.sub.l] G[member of]U [intersection]C([v.sub.1], [v.sub.i]), [v.sub.l][v.sub.j] [member of] E(G)}.

Proof: Let m[j] = max{l [member of] (1, i) | [v.sub.l] [member of] U, [v.sub.l][v.sub.j] [member of] E(G)}. Clearly,

U [intersection] C([v.sub.1], [v.sub.m[j]]] [[contains].bar] {[v.sub.l] | [v.sub.l] [member of] U [intersection]C([v.sub.1],[v.sub.i]), [v.sub.l][v.sub.j] [member of] E(G)}.

Consider any index l [member of] (1, m[j]] such that [v.sub.l] [member of] U. We want to argue that [v.sub.l] is visible from [v.sub.j]. We argue this showing that the closed polygonal path [Q.sub.l] = [v.sub.1][v.sub.l][v.sub.i][v.sub.j][v.sub.n][v.sub.1] is a convex pentagon. Note that [Q.sub.l] cannot self-intersect: all vertices are visible from [v.sub.1] and thus radially sorted around [v.sub.1] because of Lemma 1. Thus [Q.sub.l] is a polygon. We have chosen m[j] in such a way that [Q.sub.m[j]] is convex.

Since the edges [v.sub.1][v.sub.i], [v.sub.i][v.sub.n], [v.sub.j][v.sub.1], and [v.sub.n][v.sub.l] are in E(G), [Q.sub.l] has a convex angle at all vertices, but possibly at [v.sub.i]. Around [v.sub.i] we have the following circular order of visible vertices because of Lemma 1: [v.sub.j], [v.sub.n], [v.sub.1], [v.sub.l], [v.sub.m[j]]. Thus, the internal angle of [Q.sub.l] at [v.sub.i] is smaller than the internal angle of [Q.sub.m[j]] at [v.sub.i], which was convex. It follows that all angles of [Q.sub.l] are convex and thus [v.sub.j] sees [v.sub.l].

Lemma 4 Consider the setting and notation in Lemma 3. Let [v.sub.j] and [v'.sub.j]* be vertices from U [intersection] C([v.sub.i], [v.sub.n]) with j' > j. Then m[j'] [greater than or equal to] m[j].

Proof: Let [v.sub.l] and [v.sub.l'] be vertices from U [intersection] C([v.sub.1], [v.sub.i]) with l' > l. In the proof of Lemma 3 we have seen that, if [v.sub.j] (or [v.sub.j']) sees [v.sub.l'], then it also sees [v.sub.l] (in that proof we had l' = m[j], but the argument holds for any vertex in U [intersection] C([v.sub.1], [v.sub.i])). By a symmetric argument, if [v.sub.l] (or [v.sub.l']) sees [v.sub.j], then it also sees [v.sub.j'].

Therefore

{[v.sub.l] [member of] U [intersection] C([v.sub.1], [v.sub.i]) | [v.sub.l][v.sub.j] [member of] E(G)} [??] {[v.sub.l] [member og] U [intersection]C([v.sub.1], [v.sub.i]) | [v.sub.l][v.sub.j'] [member of] E(G)}

and the result follows from Lemma 3.

3 The algorithm

Let [K.sub.t] be a clique in G. An edge [v.sub.i][v.sub.j] of [K.sub.t] is lateral if all the vertices of [K.sub.t]-{[v.sub.i], [v.sub.j]} are in C([v.sub.i], [v.sub.j]) or in C([v.sub.j], [v.sub.i]). Alternatively, [v.sub.i][v.sub.j] is lateral for [K.sub.t] if [K.sub.t] is contained in any of the two polygons obtained by cutting P through the diagonal [v.sub.i][v.sub.j]. In Section 3.1 we describe a subroutine LATERALMAX-CLIQUE (G, C, e) to find a maximum clique that has e as lateral edge. This subroutine is deterministic.

The main idea of the algorithm for the general case is based on sampling several edges e of G, finding for each e a maximum clique in G that has e as lateral edge, and returning the largest of the cliques that are found. The precise details and analysis are given in Section 3.2.

Before we proceed, we give an algorithm to preprocess the representation of the graph. We assume that G is given with an arbitrary adjacency list representation. We want to have an adjacency list representation of G where, for each vertex [v.sub.i] , the list ADJ [i] has the (indices of the) neighbours of [v.sub.i] in the same order as they appear along C, starting from [v.sub.i+1] and finishing with [v.sub.i-1]. As discussed in Lemma 1, the ordering along ADJ[i] agrees with the clockwise or counterclockwise ordering of the edges emanating from [v.sub.i].

Lemma 5 We can compute in O (|E[(G)|.sup.2]/[omega](G)) time all the lists ADJ[i], [v.sub.i] [member of] V(G).

Proof: For each vertex [v.sub.i] [member of] V(G), we collect the indices of the vertices adjacent to [v.sub.i], sort them in O(deg([v.sub.i]) log(deg([v.sub.i]))) = O(deg([v.sub.i]) log |V(G)|) time, and store them in ADJ[i] sorted from i + 1 to i-1. It remains to analyze the resulting time bound. Over all vertices, this takes time

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Given that we are aiming for an algorithm whose overall running time is roughly O (|E[(G)|.sup.2]/[omega](G)), it is enough for our purposes to show that |E(G)|log|V(G)| [less than or equal to] |E[(G)|.sup.2]/[omega](G). Since |E(G)| [greater than or equal to] max {|V(G)|, [[omega].sup.2](G)}, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3.1 Maximum clique with a fixed lateral edge

Here we describe an algorithm LATERALMAXCLIQUE(G, C, e) to find a maximum clique that has agiven edge e = [v.sub.i][v.sub.j] as lateral edge. The running time of the algorithm is O(|E(G)|).

If e = [v.sub.i][v.sub.j] does not belong to the cycle C, then we can decompose P along the diagonal e into two polygons P' and P", search a largest clique containing e in each of the polygons P' and P", and return the largest of both cliques. The visibility graphs of P' and P" can be easily constructed in O(|E(G)|): one is the subgraph of G induced by C([v.sub.i], [v.sub.j]) [union] {[v.sub.i], [v.sub.j]} and the other is induced by C([v.sub.j], [v.sub.i]) [union] {[v.sub.i], [v.sub.j]}. Similarly, the cycle defining the boundary of both polygons P' and P" is easily obtained from C. Therefore, it suffices to consider the case when e belongs to the cycle C.

Our algorithm goes along the lines of a dynamic-programming algorithm by Fischer [Fis97] to solve the following problem: Given a set of points in the plane labelled either "positive" or "negative" and a positive point p, find a convex polygon Q of maximum area such that: (i) p is the bottom vertex of Q; (ii) the vertices of Q are positive points; (iii) Q does not contain any negative point. The algorithm of Fisher can easily be adapted to optimize other criteria, instead of the area, such as the number of positive points in the boundary of Q. We recommend the presentation by Bautista-Santiago et al. [BSDBL+11], where the running time of Fischer is slightly improved.

We have to make two adaptations of the idea of Fisher to our setting. First, we do not have the coordinates of the vertices so we cannot deduce which vertices are above or below some given vertex. We work around this issue by using e as a reference: the vertices that are visible from both vertices of e lie in one half plane defined by the line supporting e. Second, we adapt the dynamic programming to achieve a running time of |E(G)|. We next explain in detail the algorithm.

Without loss of generality we will assume henceforth that e = [v.sub.1][v.sub.n].

We first select the (indices of the) vertices of P that are visible from both [v.sub.1] and [v.sub.n]. Let J = {i [member of] (1, n) | [v.sub.i] visible from [v.sub.1] and [v.sub.n]}. The set J can be constructed from ADJ[1] and ADJ[n] in time O(|V(G)|)=O(|E(G)|).

For each i [member of] J let us define

[J.sub.<i] = {j [member of] J | j < i, [v.sub.j][v.sub.i] [member of] E(G)} and [J.sub.>i] = {j [member of] J | j > i, [v.sub.i][v.sub.j] [member of] E(G)}.

See Figure 4, left. Note that, for example, [J.sub.<i] uses information about the visibility from [v.sub.i]. Thus, [J.sub.<i] [union] [J.sub.>i] is potentially smaller than J. For the algorithm we will need that [J.sub.<i] and [J.sub.>i] are represented as lists storing the elements sorted in increasing order. We can construct the lists [J.sub.<i], for all i [member of] J, in O(|E(G)|) time, as follows. We first make a binary table B[1..n] such that B[j] is true if and only if j [member of] J. After this, we can construct [J.sub.<i] in time O(deg([v.sub.i])) by scanning ADJ[i]: if j [member of] ADJ[i] satisfies j < i and B[j] is true, then we add j to [J.sub.<i]. A similar approach works to construct in time O(|E(G)|) the lists [J.sub.>i], for all i [member of] J. Since the elements of ADJ[i] are sorted, we also obtain the lists [J.sub.<i] and [J.sub.>i] sorted, as desired.

If J contains one single vertex or [J.sub.<i] is empty for all i [member of] J, then the largest clique containing e as lateral edge has size 3. We assume henceforth that J has more than an element and there are some edges [v.sub.i][v.sub.j] with i, j [member of] J.

[FIGURE 4 OMITTED]

For each i [member of] J and j [member of] [J.sub.>i], we define OPT[i, j] as the number of vertices in the maximum clique that has [v.sub.i], [v.sub.j], [v.sub.n] and [v.sub.1] as consecutive vertices in the convex hull. Alternatively, OPT[i, j] is the number of vertices in the maximum clique using vertices {[v.sub.i], [v.sub.j],[v.sub.n], [v.sub.1]} and a subset of C([v.sub.1], [v.sub.i]). The algorithm finds the values OPT[i, *], i [member of] J, for increasing values of i, as follows. The following statement shows the recursive behavior of OPT[*, *].

Lemma 6 If i [member of] J and j [member of] [J.sub.>i], then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Proof: This is a standard proof in dynamic programming. We use induction on i. Consider i [member of] J and j [member of] [J.sub.>i].

If {I [member of] [J.sub.<i] | [v.sub.l][v.sub.j] [member of] E(G)} is empty, then no vertex in C([v.sub.1], [v.sub.i]) is visible simultaneously from [v.sub.1], [v.sub.n], [v.sub.i], [v.sub.j], and thus OPT[i, j] = 4, as the lemma says. This covers all base cases.

Consider the case where {[member of] [J.sub.<i] | [v.sub.l][v.sub.j] [member of] E(G)} is nonempty. We have to show that OPT[i, j] = 1 + max{OPT[l, i] | l [member of] [J.sub.<i], [v.sub.l][v.sub.j] [member of] E(G)}. We do this in two steps.

Let U [??] C([v.sub.1], [v.sub.i]) be such that U [union] {[v.sub.i], [v.sub.j], [v.sub.n], [v.sub.1]} is a maximum clique defining OPT[i, j]. Let [v.sub.t] be the vertex with highest index in U and set U' = U \ {[v.sub.t]}. Clearly t [member of] [J.sub.<i] and [v.sub.t][v.sub.j] [member of] E(G). Since U' [union] {[v.sub.t], [v.sub.i], [v.sub.n], [v.sub.1]} is a clique with U' [subset] C([v.sub.1], [v.sub.t]), we have by induction that OPT[t, i] [greater than or equal to] |U'| + 4 = |U| +3. Therefore

OPT[i, j] = |U|+4 [greater than or equal to] 1 + OPT[t, i] [greater than or equal to] 1 + max{OPT[l, i] |i [member of] [J.sub.<i], [v.sub.l][v.sub.j] [member of] E(G)}. (2)

To show the other inequality, consider l* [member of] [J.sub.<i] such that [v.sub.l]* [v.sub.j] [member of] E(G) and

OPT[l*, i] = max{OPT[l, i] | i [member of] [J.sub.<i], [v.sub.l][v.sub.j] [member of] E(G)}.

See Figure 4, right. By induction hypothesis, there exists U [??] C(1, l*) such that U [union] {[v.sub.l]*, [v.sub.i], [v.sub.n], [v.sub.1]} is a clique of size OPT[l*, i]. Since[v.sub.l]*[v.sub.j], [v.sub.i][v.sub.j], [v.sub.1][v.sub.j],[v.sub.n][v.sub.j] [member of] E(G), it follows that U [union] {[v.sub.l]*,[v.sub.i],[v.sub.j],[v.sub.n],[v.sub.1]} is a clique because of Lemma 2. Thus

OPT[i, j] [greater than or equal to] 1 + OPT[L*, i] = 1 + max{OPT[l, i] | l [member of] [J.sub.<i], [v.sub.l][v.sub.j] [member of] E(G)}. (3)

Combining Equations (2) and (3), the remaining case is done.

Using Equation (1), each value OPT[i, j] can be computed in O(deg([v.sub.i])) time. This means that all OPT[i, j], i [member of] J and j [member of] [J.sub.>i] can be computed in [O((deg([v.sub.i])).sup.2]) time. However, this can be done faster by using a few additional observations, as we will show next.

Lemma 7 Assume that the values OPT[l, i] are already available for each i [member of] [J.sub.<i]. Then we can compute the values OPT[i, j] for all j [member of] [J.sub.>i] in O(deg([v.sub.i])) time.

Proof: We obtain the values OPT[i, *] in increasing order of the second term. We use the following properties; see Lemmas 3 and 4:

* For each j [member of] [J.sub.>i], there is a value m[j] [member of] [J.sub.<i] such that

[J.sub.<i] [intersection] (1, m[j]] = {l [member of] [J.sub.<i] | [v.sub.l][v.sub.j] [memebr of] E(G)}.

* If j, j' [member of] [J.sub.>i] and j < j', then m[j] [greater than or equal to] m[j']. In other words, m[j] is nondecreasing in j [member of] [J.sub.>i].

For each l [member of] [J.sub.<i], let

B[l] = max{OPT[l', i] | l' [member of] [J.sub.<i], l' [greater than or equal to] l}.

We compute the values B[l], l [member of] [J.sub.<i], in O(deg([v.sub.i])) by scanning OPT[*, i] and keeping the prefix maximum.

Next, we compute the index m[j] for all j [member of] [J.sub.>i] in O(deg([v.sub.i])) time. This is a simple loop with two indices; details are provided in Figure 5. Here it is useful to treat [J.sub.<i] and [J.sub.>i] as lists where the elements are stored in increasing order. Finally, we use that, for each j [member of] [J.sub.>i]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since the tables B[*] and m[*] can be computed in O(deg([v.sub.i])) time, the result follows.

When the entire table OPT[*, *] has been filled, we traverse it to find its maximum value. This maximum value is precisely LATERALMAXCLIQUE(G, C, e). Notice that we can also find a largest clique containing e by augmenting each entry of the table OPT with extra information: for a given position [i, j] we also store the value t such that OPT[i, j] = OPT[t, i] + 1. We conclude the following.
Algorithm FINDING m[j]
(* We treat [J.sub.<i] and [J.sub.>i] as lists storing the indices in
increasing order *)
1.  j [left arrow] first element in [J.sub.>i];
2.  l [left arrow] first element in [J.sub.<i];
3.  while j [not equal to] NULL and l [not equal to] NULL
4.   if [v.sub.l][v.sub.j] [member of] E(G) then
5.    m[j] [left arrow] l;
6.    l [left arrow] element after l in [J.sub.<i];
7.   else
8.    j [left arrow] element after j in [J.sub.>i];
9.    m[j] [left arrow] element before l in [J.sub.<i];

Figure 5: Algorithm used in the proof of Lemma 7.


Lemma 8 There is an algorithm LATERALMAXCLIQUE(G, C, e) that, after O(|E[(G)|.sup.2]/[omega](G)) preprocessing time, has the following property: for any given e [member of] E(G) we can find in time O(|E(G)|) a maximum-size clique in G that has e as lateral edge.

Proof: We preprocess the graph as discussed in Lemma 5. After this, we compute the entries OPT[i, j], j [member of] [J.sub.>i], for increasing values of i [member of] J. Using Lemma 7, we spend O(deg([v.sub.i])) per i [member of] J. So the total time to compute all entries OPT[*, *] is [member of] ([[summation].sub.i[member of]J] deg([v.sub.i])) = O(|E(G)|). Finally, we return max{OPT[i, j] | i [member of] J, j [member of] [J.sub.>i]} and a clique of this size, which can be reconstructed from the extra information stored at each entry of the table OPT. Correctness follows from the definition of OPT[*, *].

3.2 General case

Calling LATERALMAXCLIQUE(G, C, e) for each edge e [member of] E(G) and returning the largest clique that is found, we obtain the following result.

Theorem 9 Given the visibility graph G of a simple polygon P and a Hamiltonian cycle describing the order of the vertices of P along its boundary, we can compute a maximum clique in time O(|E[(G)|.sup.2]).

We now describe a randomized variant. In Figure 6 we give the algorithm RANDMAXCLIQUE.

Theorem 10 Given the visibility graph G of a simple polygon P, a Hamiltonian cycle describing the order of the vertices of P along its boundary, and a parameter [delta] [member of] (0,1), with probability at least 1 - [delta], RANDMAXCLIQUE computes a clique in G of maximum size in time [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Since [omega] is smaller than or equal to [omega](G), the condition to exit the repeat loop implies that there are at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

iterations of the repeat loop.

Let A be the event that, in the first m(G, [delta]) iterations of the repeat loop, at least once we select an edge e that is lateral for a maximum-size clique. If the event A occurs, then:
Algorithm RANDMAXCLIQUE
Input: graph G, Hamiltonian cycle C, parameter [delta] [member of] (0,
1)
Output: maximum clique in G with probability at least 1-[delta]
1.  Preprocess G to solve LATERALMAXCLIQUE; (* Lemma 8 *)
2.  [omega][left arrow] 0; (* size largest found clique *)
3.  i[left arrow]0; (* counter number of iterations *)
4.  repeat
5.   choose edge e [member of] E(G) uniformly at random;
6.   [omega] [left arrow] max{[omega], LATERALMAXCLIQUE(G, C, e)}
7.   i [left arrow] i + 1;
8.  until [omega] [greater than or equal to] (\E(G)\/i) ln(1/[delta])
9.  return [omega]

Figure 6: Algorithm RANDMAXCLIQUE.


* the algorithm returns [omega](G), and

* there are exactly m(G, [delta]) iterations of the repeat loop, so the time complexity is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

because of Lemma 8.

We next show that A occurs with probability at least 1-[delta], which finishes the proof. Consider any iteration of the repeat loop. Since a maximum-size clique has [omega](G) lateral edges, with probability at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the selected edge e is lateral for some maximum-size clique. Let [A.sup.c] be the complement of A: in each of the first m(G, [delta]) iterations, e is not a lateral edge for any maximum-size clique. The probability of [A.sup.c] is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where we have used that [(1 - 1/x).sup.x] [less than or equal to] 1/e holds for any x [member of] R. Thus, the event A occurs with probability at least 1-[delta] and the proof is finished.

References
[AR85]             David Avis and David Rappaport. Computing the
                   largest empty convex subset of a set of
                   points. In Proc. 1st Symp. Computational Geometry,
                   pages 161-167. ACM, 1985.
[[BSDBL.sup.+]11]  Crevel Bautista-Santiago, Jose Miguel Diaz-Banez,
                   Dolores Lara, Pablo Perez-Lantero,
                   Jorge Urrutia, and Inmaculada Ventura. Computing
                   optimal islands. Oper. Res. Lett.,
                   39(4):246-251, 2011.
[Cha91]            Bernard Chazelle. Triangulating a simple polygon in
                   linear time. Discrete & Computational
                   Geometry, 6:485-524, 1991.
[Fis97]            Paul Fischer. Sequential and parallel algorithms
                   for finding a maximum convex polygon.
                   Comput. Geom., 7(3):187-200, 1997.
[GG13]             Subir Kumar Ghosh and Partha Pratim Goswami.
                   Unsolved problems in visibility graphs
                   of points, segments, and polygons. ACM Comput.
                   Surv., 46(2):22, 2013.
[Gho97]            Subir Kumar Ghosh. On recognizing and
                   characterizing visibility graphs of simple polygons.
                   Discrete Comput. Geom., 17(2):143-162, 1997.
[Gho07]            Subir Kumar Ghosh. Visibility Algorithms in the
                   Plane. Cambridge University Press, 2007.
[GM91]             Subir Kumar Ghosh and David M. Mount. An
                   output-sensitive algorithm for computing
                   visibility graphs. SIAM J. Comput., 20(5):888-910,
                   1991.
[GSBG07]           Subir Kumar Ghosh, Thomas C. Shermer, Binay K.
                   Bhattacharya, and Partha P. Goswami.
                   Computing the maximum clique in the visibility
                   graph of a simple polygon. J. Discrete
                   Algorithms, 5(3):524-532, 2007.
[Her89]            John Hershberger. An optimal visibility graph
                   algorithm for triangulated simple polygons.
                   Algorithmica, 4(1):141-155, 1989.


Sergio Cabello (1*) Maria Saumell (2[dagger])

(1) Department of Mathematics, IMFM and FMF, University of Ljubljana, Slovenia

(2) Department of Mathematics and European Centre of Excellence NTIS, University of West Bohemia, Czech Republic

received 18th Oct. 2013, revised 28th Nov. 2014, accepted 15th Dec. 2014.

(*) Email: sergio.cabello@fmf.uni-lj.si. Supported by the Slovenian Research Agency, program P1-0297, projects J1-4106 and L7-5459, and within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation.

([dagger]) Email: saumell@kma.zcu.cz. Supported by projects NEXLIZ - CZ.1.07/2.3.00/30.0038, which is co-financed by the European Social Fund and the state budget of the Czech Republic, and ESF EuroGIGA project ComPoSe as F.R.S.-FNRS - EU-ROGIGA NR 13604.
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Cabello, Sergio; Saumell, Maria
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2015
Words:5901
Previous Article:The double competition multigraph of a digraph.
Next Article:Ore-degree threshold for the square of a Hamiltonian cycle.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters