Full text
Preview |
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (442kB) | Preview |
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.
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 |
Preview |
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (442kB) | Preview |
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.
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 |