Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/21926
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBarba, Luispt
dc.contributor.authorKorman, Matiaspt
dc.contributor.authorLangerman, Stefanpt
dc.contributor.authorSilveira, Rodrigopt
dc.date.accessioned2018-01-30T11:48:12Z-
dc.date.available2018-01-30T11:48:12Z-
dc.date.issued2014-
dc.identifier.issn0925-7721pt
dc.identifier.urihttp://hdl.handle.net/10773/21926-
dc.description.abstractWe present several algorithms for computing the visibility polygon of a simple polygon P of n vertices (out of which r are reflex) from a viewpoint inside P, when P resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O(nr¯) time, where r¯ denotes the number of reflex vertices of P that are part of the output. Whenever we are allowed to use O(s) variables, the running time decreases to O(nr2s+nlog2r) (or O(nr2s+nlogr) randomized expected time), where s∈O(logr). This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained.pt
dc.language.isoengpt
dc.publisherElsevierpt
dc.relationinfo:eu-repo/grantAgreement/FCT/5876/135976/PTpt
dc.relationinfo:eu-repo/grantAgreement/FCT/SFRH/SFRH%2FBPD%2F88455%2F2012/PTpt
dc.rightsopenAccesspor
dc.subjectComputational geometrypt
dc.subjectMemory-constrained algorithmspt
dc.subjectTime-space-trade-off visibilitypt
dc.subjectSimple polygonpt
dc.titleComputing a visibility polygon using few variablespt
dc.typearticlept
dc.peerreviewedyespt
ua.distributioninternationalpt
degois.publication.firstPage918pt
degois.publication.issue9pt
degois.publication.lastPage926pt
degois.publication.titleComputational Geometry: Theory and Applicationspt
degois.publication.volume47pt
dc.identifier.doi10.1016/j.comgeo.2014.04.001pt
Appears in Collections:CIDMA - Artigos
CHAG - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
1111.3584.pdfartigo430.9 kBAdobe PDFView/Open


FacebookTwitterLinkedIn
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.