Guarding Vertices versus Guarding Edges in a Simple Polygon

Olivier Devillers 1 Naji Mouawad 2
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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.
Type de document :
Communication dans un congrès
4th Canadian Conference on Computational Geometry, 1992, St. John's, Canada. pp.99-102, 1992
Liste complète des métadonnées


https://hal.inria.fr/hal-01117277
Contributeur : Olivier Devillers <>
Soumis le : jeudi 19 février 2015 - 11:13:03
Dernière modification le : jeudi 11 janvier 2018 - 16:39:42
Document(s) archivé(s) le : jeudi 28 mai 2015 - 16:02:32

Fichiers

cccg92.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01117277, version 1

Collections

Citation

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, 1992. 〈hal-01117277〉

Partager

Métriques

Consultations de la notice

161

Téléchargements de fichiers

89