Article
On finding widest empty curved corridors
Author/s | Bereg, Sergey
Díaz Báñez, José Miguel Seara Ojea, Carlos Ventura Molina, Inmaculada |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) |
Publication Date | 2007 |
Deposit Date | 2018-08-10 |
Published in |
|
Abstract | 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 ... 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. |
Citation | 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
1-s2.0-S0925772107000260-main.pdf | 351.3Kb | [PDF] | View/ | |