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

研究成果: Comment/debate

摘要

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.

原文	English
頁（從 - 到）	55-60
頁數	6
期刊	Information Processing Letters
卷	85
發行號	1
DOIs	https://doi.org/10.1016/S0020-0190(02)00414-3
出版狀態	Published - 16 1月 2003
對外發佈	是

存取文件

10.1016/S0020-0190(02)00414-3

其它文件與鏈接

Link to publication in Scopus

引用此

@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

摘要

存取文件

其它文件與鏈接

指紋

引用此