Ponencia
Finding a widest empty 1-corner corridor
Autor/es | Díaz Báñez, José Miguel
López, Mario A. Sellarès Chiva, Joan Antoni |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-02 |
Resumen | Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We star giving a characterization of the 1-corner corridors that we call locally widest. Our approach to finding ... Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We star giving a characterization of the 1-corner corridors that we call locally widest. Our approach to finding a widest empty 1-corner corridor consists of identifying a set of 1-corner corridors locally widest, that is guaranteed to contain a solution. We describe an algorithm that solves the problem in O(n4 log n) time and O(n) space. |
Identificador del proyecto | BFM2000-1052
DMS-0107628 TIC2001-2392-C03-01 DURSI-2001SGR-00296 |
Cita | Díaz Báñez, J.M., López, M.A. y Sellarès Chiva, J.A. (2004). Finding a widest empty 1-corner corridor. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Finding a widest empty 1-corner ... | 123.9Kb | [PDF] | Ver/ | |