Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/21926
Título: | Computing a visibility polygon using few variables |
Autor: | Barba, Luis Korman, Matias Langerman, Stefan Silveira, Rodrigo |
Palavras-chave: | Computational geometry Memory-constrained algorithms Time-space-trade-off visibility Simple polygon |
Data: | 2014 |
Editora: | Elsevier |
Resumo: | 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 |
Aparece nas coleções: | CIDMA - Artigos CHAG - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
1111.3584.pdf | artigo | 430.9 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.