Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient Algorithms for Guarding or Illuminating the Surface of a Polyhedral Terrain (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bose, Prosenjit Kirkpatrick, David Li, Zaiqing |
| Description | We present efficient polynomial time algorithms that place bn=2c vertex guards which cover the surface of an n-vertex polyhedral terrain, and similarly, bn=3c edge guards which cover the surface of an n-vertex polyhedral terrain. The time complexity of both algorithms, dominated by the cost of finding a maximum matching in a graph, is O(n ). |
| File Format | |
| Language | English |
| Publisher | Carleton University Press |
| Publisher Date | 1996-01-01 |
| Publisher Institution | Proceedings of the 8th Canadian Conference on Computational Geometry, volume 5 of International Informatics Series |
| Access Restriction | Open |
| Subject Keyword | N-vertex Polyhedral Terrain Efficient Polynomial Time Algorithm Vertex Guard Efficient Algorithm Polyhedral Terrain Edge Guard Maximum Matching Time Complexity |
| Content Type | Text |
| Resource Type | Article |
