Cabello, Sergio and Saumell, Maria - A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon

dmtcs:2126 - Discrete Mathematics & Theoretical Computer Science, January 21, 2015, Vol. 17 no. 1 (in progress)
A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon

Authors: Cabello, Sergio and Saumell, Maria

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.


Source : oai:HAL:hal-01196870v1
Volume: Vol. 17 no. 1 (in progress)
Section: Discrete Algorithms
Published on: January 21, 2015
Submitted on: October 18, 2013
Keywords: randomized algorithm,visibility graph,maximum clique,simple polygon,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]


Share

Browsing statistics

This page has been seen 18 times.
This article's PDF has been downloaded 59 times.