Escondiendo puntos en espirales e histogramas

Bajuelos Domínguez, Antonio Leslie; Canales Cano, Santiago; Hernández Peñalver, Gregorio y Martins, Ana Mafalda (2008). Escondiendo puntos en espirales e histogramas. En: "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.

Descripción

Título: Escondiendo puntos en espirales e histogramas
Autor/es:
  • Bajuelos Domínguez, Antonio Leslie
  • Canales Cano, Santiago
  • Hernández Peñalver, Gregorio
  • Martins, Ana Mafalda
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: VI Jornadas de Matemática Discreta y Algorítmica, JMDA'08
Fechas del Evento: 21/07/2008-23/07/2008
Lugar del Evento: Lerida, España
Título del Libro: Actas de las VI Jornadas de Matemática Discreta y Algorítmica, JMDA'08
Fecha: 2008
ISBN: 978-84-8409-263-6
Materias:
Palabras Clave Informales: Visibilidad, puntos ocultos, espiral, histograma.
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (442kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 4564
Identificador DC: http://oa.upm.es/4564/
Identificador OAI: oai:oa.upm.es:4564
URL Oficial: http://www.jmda2008.udl.cat/html/programa.html
Depositado por: Memoria Investigacion
Depositado el: 15 Oct 2010 10:24
Ultima Modificación: 20 Abr 2016 13:43
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM