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