Back to Search
Start Over
Improved Algorithm for a Widest 1-Corner Corridor.
- Source :
- Walcom: Algorithms & Computation (9783642002014); 2009, p83-92, 10p
- Publication Year :
- 2009
-
Abstract
- Given a set P of n points on a 2D plane, the 1-corner empty corridor is a region inside the convex hull of P which is bounded by a pair of links; each link is an unbounded trapezium bounded by two parallel half-lines, and it does not contain any point of P. We present an improved algorithm for computing the widest empty 1-corner corridor that runs in O(n<superscript>3</superscript>log<superscript>2</superscript>n) time and O(n<superscript>2</superscript>) space. This improves the time complexity of the best known algorithm for the same problem by a factor of ]> [4]. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642002014
- Database :
- Complementary Index
- Journal :
- Walcom: Algorithms & Computation (9783642002014)
- Publication Type :
- Book
- Accession number :
- 76732824
- Full Text :
- https://doi.org/10.1007/978-3-642-00202-1_8