| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Guarding Vertices versus Guarding Edges in a Simple Polygon
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.
https://hal.inria.fr/hal-01117277
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, February 19, 2015 - 11:13:03 AM
Last modification on : Friday, January 21, 2022 - 4:10:00 AM
Long-term archiving on: : Thursday, May 28, 2015 - 4:02:32 PM
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, February 19, 2015 - 11:13:03 AM
Last modification on : Friday, January 21, 2022 - 4:10:00 AM
Long-term archiving on: : Thursday, May 28, 2015 - 4:02:32 PM
Files
cccg92.pdf
Files produced by the author(s)