|
|||||
|
|
On finding widest empty curved corridors |
|
| Authors: | Sergey Bereg J Miguel Díaz-Bez Carlos Seara Inmaculada Ventura |
| Institution: | aDepartment of Computer Science, University of Texas at Dallas, Box 830688, Richardson, TX 75083, USA bDepartamento de Matemática Aplicada II, Universidad de Sevilla, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain cDepartament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, 08034 Barcelona, Spain dDepartamento de Matemáticas, Universidad de Huelva, Spain |
| 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 , we want to compute the widest empty -siphon that splits P into two non-empty sets. We present an efficient O(nlog3n)-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(n3log2n)-time algorithm for the widest arbitrarily-oriented version and an Θ(nlogn)-time algorithm for the widest arbitrarily-oriented -siphon anchored at a given point. |
| Keywords: | Corridors Geometric optimization Facility location |
| 本文献已被 ScienceDirect 等数据库收录！ | |