Transversal of disjoint convex polygons

Francis Y.L. Chin; Hong Shen; Fu Lee Wang

doi:10.1016/S0020-0190(02)00414-3

Transversal of disjoint convex polygons

Francis Y.L. Chin
, Hong Shen
, Fu Lee Wang

The University of Hong Kong
Japan Advanced Institute of Science and Technology
Chinese University of Hong Kong

Research output: Contribution to journal › Comment/debate

Abstract

A report on the transversal of disjoint convex polygons was presented. The existence of an ω(nlogn) lower bound for finding a transversal of n homothets of a circle was shown. The results for the n parallel line segments transversal problem was further extended to show that a transversal of n rectangles could also be found in O(n) time.

Original language	English
Pages (from-to)	55-60
Number of pages	6
Journal	Information Processing Letters
Volume	85
Issue number	1
DOIs	https://doi.org/10.1016/S0020-0190(02)00414-3
Publication status	Published - 16 Jan 2003
Externally published	Yes

Keywords

Computational geometry
Disjoint convex polygon
Stabber
Transversal

Access to Document

10.1016/S0020-0190(02)00414-3

Cite this

@article{6e0afff1307846bb9e5e1d9f630b49ce,

title = "Transversal of disjoint convex polygons",

abstract = "A report on the transversal of disjoint convex polygons was presented. The existence of an ω(nlogn) lower bound for finding a transversal of n homothets of a circle was shown. The results for the n parallel line segments transversal problem was further extended to show that a transversal of n rectangles could also be found in O(n) time.",

keywords = "Computational geometry, Disjoint convex polygon, Stabber, Transversal",

author = "Chin, \{Francis Y.L.\} and Hong Shen and Wang, \{Fu Lee\}",

note = "Funding Information: ✩This research is supported by RGC Research Grant HKU 7024/98E. ✩✩ PII of original article: S0020-0190(01)00322-2. * Corresponding author. E-mail addresses: [email protected] (F.Y.L. Chin), [email protected] (H. Shen), [email protected] (F.L. Wang).",

year = "2003",

month = jan,

day = "16",

doi = "10.1016/S0020-0190(02)00414-3",

language = "English",

volume = "85",

pages = "55--60",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

number = "1",

}

TY - JOUR

T1 - Transversal of disjoint convex polygons

AU - Chin, Francis Y.L.

AU - Shen, Hong

AU - Wang, Fu Lee

N1 - Funding Information: ✩This research is supported by RGC Research Grant HKU 7024/98E. ✩✩ PII of original article: S0020-0190(01)00322-2. * Corresponding author. E-mail addresses: [email protected] (F.Y.L. Chin), [email protected] (H. Shen), [email protected] (F.L. Wang).

PY - 2003/1/16

Y1 - 2003/1/16

N2 - A report on the transversal of disjoint convex polygons was presented. The existence of an ω(nlogn) lower bound for finding a transversal of n homothets of a circle was shown. The results for the n parallel line segments transversal problem was further extended to show that a transversal of n rectangles could also be found in O(n) time.

AB - A report on the transversal of disjoint convex polygons was presented. The existence of an ω(nlogn) lower bound for finding a transversal of n homothets of a circle was shown. The results for the n parallel line segments transversal problem was further extended to show that a transversal of n rectangles could also be found in O(n) time.

KW - Computational geometry

KW - Disjoint convex polygon

KW - Stabber

KW - Transversal

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

U2 - 10.1016/S0020-0190(02)00414-3

DO - 10.1016/S0020-0190(02)00414-3

M3 - Comment/debate

AN - SCOPUS:0037448289

SN - 0020-0190

VL - 85

SP - 55

EP - 60

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Transversal of disjoint convex polygons

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this