Opened Access On finding widest empty curved corridors

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Bereg, Sergey
Díaz Báñez, José Miguel
Seara, Carlos
Ventura Molina, Inmaculada
Departamento: Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI)
Fecha: 2007
Publicado en: Computational Geometry, 38 (3), 154-169.
Tipo de documento: Artículo
Resumen: An α-siphon of width w is the locus of points in the plane that are at the same distance w from a 1-corner polygonal chain C such that α is the interior angle of C. Given a set P of n points in the plane and a fixed angle α, we want to compute the widest empty α-siphon that splits P into two non-empty sets.We present an efficient O(n log3 n)-time algorithm for computing the widest oriented α-siphon through P such that the orientation of a half-line of C is known.We also propose an O(n3 log2 n)-time algorithm for the widest arbitrarily-oriented version and an (nlog n)-time algorithm for the widest arbitrarily-oriented α-siphon anchored at a given point.
Cita: Bereg, S., Díaz Báñez, J.M., Seara, C. y Ventura Molina, I. (2007). On finding widest empty curved corridors. Computational Geometry, 38 (3), 154-169.
Tamaño: 351.3Kb
Formato: PDF

URI: https://hdl.handle.net/11441/77996

DOI: 10.1016/j.comgeo.2007.02.003

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones