Guarding the vertices of thin orthogonal polygons is NP-hard

Nunes Gomes Tomás, Ana Paula

Ponencia

dc.contributor.editor	Díaz Báñez, José Miguel	es
dc.contributor.editor	Garijo Royo, Delia	es
dc.contributor.editor	Márquez Pérez, Alberto	es
dc.contributor.editor	Urrutia Galicia, Jorge	es
dc.creator	Nunes Gomes Tomás, Ana Paula	es
dc.date.accessioned	2017-05-18T07:14:40Z
dc.date.available	2017-05-18T07:14:40Z
dc.date.issued	2013
dc.identifier.citation	Nunes Gomes Tomás, A.P. (2013). Guarding the vertices of thin orthogonal polygons is NP-hard. En XV Spanish Meeting on Computational Geometry, Sevilla.
dc.identifier.uri	http://hdl.handle.net/11441/60003
dc.description.abstract	An orthogonal polygon of P is called “thin” if the dual graph of the partition obtained by extending all edges of P towards its interior until they hit the boundary is a tree. We show that the problem of computing a minimum guard set for either a thin orthogonal polygon or only its vertices is NP-hard, indeed APX-hard, either for guards lying on the boundary or on vertices of the polygon.	es
dc.description.sponsorship	Fondo Europeo de Desarrollo Regional	es
dc.description.sponsorship	Fundação para a Ciência e a Tecnologia	es
dc.format	application/pdf	es
dc.language.iso	eng	es
dc.relation.ispartof	XV Spanish Meeting on Computational Geometry (2013), pp. 19-22.
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 Internacional	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/	*
dc.title	Guarding the vertices of thin orthogonal polygons is NP-hard	es
dc.type	info:eu-repo/semantics/conferenceObject	es
dcterms.identifier	https://ror.org/03yxnpp24
dc.type.version	info:eu-repo/semantics/publishedVersion	es
dc.rights.accessRights	info:eu-repo/semantics/openAccess	es
dc.contributor.affiliation	Universidad de Sevilla. Departamento de Matemática Aplicada II
dc.relation.projectID	PEst-C/MAT/UI0144/2011	es
dc.relation.publisherversion	http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf	es
idus.format.extent	4 p.	es
dc.publication.initialPage	19	es
dc.publication.endPage	22	es
dc.eventtitle	XV Spanish Meeting on Computational Geometry	es
dc.eventinstitution	Sevilla	es

Ficheros	Tamaño	Formato	Ver	Descripción
Guarding the vertices of thin ...	1.234Mb	[PDF]	Ver/Abrir

Este registro aparece en las siguientes colecciones

Mostrar el registro sencillo del ítem

Excepto si se señala otra cosa, la licencia del ítem se describe como: Attribution-NonCommercial-NoDerivatives 4.0 Internacional