Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Computing a visibility polygon using few variables

Autor
Barba, L.; Korman, M.; Langerman, S.; Silveira, R.I.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2014-10-01
Volum
47
Número
9
Pàgina inicial
918
Pàgina final
926
DOI
https://doi.org/10.1016/j.comgeo.2014.04.001 Obrir en finestra nova
Projecte finançador
Morfología geométrica computacional.
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
Repositori
http://hdl.handle.net/2117/24062 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0925772114000509 Obrir en finestra nova
Resum
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 (n (r) over bar) time, where (r) over bar denotes the number of reflex vertices of P that are part of the output. Whenever we are allowed to use O(s) ...
Citació
Barba, L. [et al.]. Computing a visibility polygon using few variables. "Computational geometry: theory and applications", 01 Octubre 2014, vol. 47, núm. 9, p. 918-926.
Paraules clau
Computational geometry, LIMITED STORAGE, Memory-constrained algorithms, Simple polygon, Time-space-trade-off visibility, UPPER-BOUNDS
Grup de recerca
CGA -Computational Geometry and Applications

Participants