Guarding Vertices versus Guarding Edges in a Simple Polygon - Archive ouverte HAL Access content directly
Conference Papers Year : 1992

## Guarding Vertices versus Guarding Edges in a Simple Polygon

(1) , (2)
1
2
Olivier Devillers
• Function : Author

#### Abstract

Let $P$ be a simple polygon, $V$ its set of vertices. A minimal vertex cover $C$ of $P$ is a minimal subset of $V$ which covers $V$. The extended cover of $P$ given $C$ is the maximal subset of the boundary of $P$ covered by $C$. Let $\epsilon P$ denotes the extended cover of $P$ given $C$, and $\bar{\epsilon}P$ the complement of $\epsilon P$ with respect to $\delta P$. Denote by $\mu$ the cardinality of $\bar{\epsilon}P$. In this paper we establish lower and upper bounds on $\mu$ as a function of $n$ the cardinality of the edge set of $P$ and $k$ the cardinality of the covering set. In the restricted case where $k = 2$ we prove the bounds to be tight.

### Dates and versions

hal-01117277 , version 1 (19-02-2015)

### Identifiers

• HAL Id : hal-01117277 , version 1

### Cite

Olivier Devillers, Naji Mouawad. Guarding Vertices versus Guarding Edges in a Simple Polygon. 4th Canadian Conference on Computational Geometry, 1992, St. John's, Canada. pp.99-102. ⟨hal-01117277⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

81 View