Widest empty L-shaped corridor

Siu Wing Cheng

doi:10.1016/0020-0190(96)00070-1

Widest empty L-shaped corridor

Siu Wing Cheng^*

^*Corresponding author for this work

Department of Computer Science and Engineering

Research output: Contribution to journal › Journal Article › peer-review

19 Citations (Scopus)

Abstract

Given a set of n points in the plane, we consider the problem of computing the widest empty L-shaped corridor. Our algorithm runs in O(n³) time and O(n³) space.

Original language	English
Pages (from-to)	277-283
Number of pages	7
Journal	Information Processing Letters
Volume	58
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(96)00070-1
Publication status	Published - 24 Jun 1996

Keywords

Algorithms
Computational geometry
Persistent search tree

Access to Document

10.1016/0020-0190(96)00070-1

Cite this

@article{4adc74dc20284ca79e68e5924333c1bc,

title = "Widest empty L-shaped corridor",

abstract = "Given a set of n points in the plane, we consider the problem of computing the widest empty L-shaped corridor. Our algorithm runs in O(n3) time and O(n3) space.",

keywords = "Algorithms, Computational geometry, Persistent search tree",

author = "Cheng, \{Siu Wing\}",

year = "1996",

month = jun,

day = "24",

doi = "10.1016/0020-0190(96)00070-1",

language = "English",

volume = "58",

pages = "277--283",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Widest empty L-shaped corridor

AU - Cheng, Siu Wing

PY - 1996/6/24

Y1 - 1996/6/24

N2 - Given a set of n points in the plane, we consider the problem of computing the widest empty L-shaped corridor. Our algorithm runs in O(n3) time and O(n3) space.

AB - Given a set of n points in the plane, we consider the problem of computing the widest empty L-shaped corridor. Our algorithm runs in O(n3) time and O(n3) space.

KW - Algorithms

KW - Computational geometry

KW - Persistent search tree

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:A1996VA91800003

UR - https://openalex.org/W1970154420

UR - https://www.scopus.com/pages/publications/0042953282

U2 - 10.1016/0020-0190(96)00070-1

DO - 10.1016/0020-0190(96)00070-1

M3 - Journal Article

SN - 0020-0190

VL - 58

SP - 277

EP - 283

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Widest empty L-shaped corridor

Abstract

Keywords

Access to Document

Other files and links

Cite this