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

*Sergio Cabello, Maria Saumell*

#### Abstract

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
δ∈(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-δ the algorithm runs in O(
|E(G)|

^{2}/ ω(G) log(1/δ)) time and returns a maximum clique, where ω(G) is the number of vertices in a maximum clique in G. A deterministic variant of the algorithm takes O(|E(G)|^{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)|^{2}|E(G)|) time.Full Text: PDF PostScript