Título:
|
Computing a visibility polygon using few variables
|
Autor/a:
|
Barba, Luis; Korman Cozzetti, Matías; Langerman, Stefan; Silveira, Rodrigo Ignacio
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
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 (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) variables, the running time decreases to O (nr/2(s) + n log(2) r) (or O (nr/2(s) + n log r) randomized expected time), where s is an element of O (log r). This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained. (C) 2014 Elsevier B.V. All rights reserved. |
Abstract:
|
Peer Reviewed |
Materia(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional -Computational geometry -Computational geometry -Memory-constrained algorithms -Time-space-trade-off visibility -Simple polygon -LIMITED STORAGE -UPPER-BOUNDS -Geometria computacional |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Artículo |
Compartir:
|
|