Presentation
Finding a widest empty 1-corner corridor
Author/s | Díaz Báñez, José Miguel
López, Mario A. Sellarès Chiva, Joan Antoni |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) |
Publication Date | 2004 |
Deposit Date | 2017-03-02 |
Abstract | 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. |
Project ID. | BFM2000-1052
DMS-0107628 TIC2001-2392-C03-01 DURSI-2001SGR-00296 |
Citation | 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Finding a widest empty 1-corner ... | 123.9Kb | [PDF] | View/ | |