Full text
Preview |
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (442kB) | Preview |
Escondiendo puntos en espirales e histogramas
Citation
Bajuelos Domínguez, Antonio Leslie and Canales Cano, Santiago and Hernández Peñalver, Gregorio and Martins, Ana Mafalda (2008). Escondiendo puntos en espirales e histogramas. In: "VI Jornadas de Matemática Discreta y Algorítmica, JMDA'08", 21/07/2008-23/07/2008, Lerida, España. ISBN 978-84-8409-263-6.
Description
| Title: | Escondiendo puntos en espirales e histogramas |
|---|---|
| Author/s: |
|
| Item Type: | Presentation at Congress or Conference (Article) |
| Event Title: | VI Jornadas de Matemática Discreta y Algorítmica, JMDA'08 |
| Event Dates: | 21/07/2008-23/07/2008 |
| Event Location: | Lerida, España |
| Title of Book: | Actas de las VI Jornadas de Matemática Discreta y Algorítmica, JMDA'08 |
| Date: | 2008 |
| ISBN: | 978-84-8409-263-6 |
| Subjects: | |
| Freetext Keywords: | Visibilidad, puntos ocultos, espiral, histograma. |
| Faculty: | Facultad de Informática (UPM) |
| Department: | Matemática Aplicada |
| Creative Commons Licenses: | Recognition - No derivative works - Non commercial |
Abstract
El problema de maximizar el número de vértices que no son visibles dos a dos en un polígono simple P, (MAXIMUN HIDDEN VERTEX SET) es un problema NP-duro [6]. En este trabajo se resuelve el problema para dos tipos de polígonos: espirales e histogramas. Para los primeros se obtiene un algoritmo lineal que resuelve el problema MHVS y cotas para el máximo número h de vértices ocultos, [r2 ]+ 1 ≤ h ≤ r + 1, siendo r el número de vértices cóncavos del polígono espiral. Para polígonos histograma se demuestra que h = r − (p − 1), siendo p el número de lados fondo.
More information
| Item ID: | 4564 |
|---|---|
| DC Identifier: | https://oa.upm.es/4564/ |
| OAI Identifier: | oai:oa.upm.es:4564 |
| Official URL: | http://www.jmda2008.udl.cat/html/programa.html |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 15 Oct 2010 10:24 |
| Last Modified: | 20 Apr 2016 13:43 |
