Escondiendo puntos en espirales e histogramas

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:
  • Bajuelos Domínguez, Antonio Leslie
  • Canales Cano, Santiago
  • Hernández Peñalver, Gregorio
  • Martins, Ana Mafalda
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

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (442kB) | Preview

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: http://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
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM