Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/21926
Title: Computing a visibility polygon using few variables
Author: Barba, Luis
Korman, Matias
Langerman, Stefan
Silveira, Rodrigo
Keywords: Computational geometry
Memory-constrained algorithms
Time-space-trade-off visibility
Simple polygon
Issue Date: 2014
Publisher: Elsevier
Abstract: We 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.
Peer review: yes
URI: http://hdl.handle.net/10773/21926
DOI: 10.1016/j.comgeo.2014.04.001
ISSN: 0925-7721
Appears in Collections:CIDMA - Artigos
CHAG - Artigos
OGTCG - Artigos

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


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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