|
|||||
|
|
Computing the maximum clique in the visibility graph of a simple polygon |
|
| Authors: | Subir Kumar Ghosh Thomas Caton Shermer Binay Kumar Bhattacharya Partha Pratim Goswami |
| Institution: | aSchool of Computer Science, Tata Institute of Fundamental Research, Mumbai 400005, India;bSchool of Computing Science, Simon Fraser University, Burnaby, B.C. Canada V5A 1S6;cDepartment of Computer Science and Engineering, University of Kalyani, Nadia, West Bengal 742135, India |
| Abstract: | In this paper, we present an algorithm for computing the maximum clique in the visibility graph G of a simple polygon P in O(n2e) time, where n and e are number of vertices and edges of G respectively. We also present an O(ne) time algorithm for computing the maximum hidden vertex set in the visibility graph G of a convex fan P. We assume in both algorithms that the Hamiltonian cycle in G that corresponds to the boundary of P is given as an input along with G. |
| Keywords: | Algorithm Convexity Convex fan Dynamic programming Hamiltonian cycle Hidden vertex set Maximum clique Simple polygon Visibility graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |