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 - http://www.scopus.com/inward/record.url?scp=0037448289&partnerID=8YFLogxK
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 -