Efficient algorithm for transversal of disjoint convex polygons

Francis Y.L. Chin; Fu Lee Wang

doi:10.1016/S0020-0190(01)00322-2

Efficient algorithm for transversal of disjoint convex polygons

Francis Y.L. Chin, Fu Lee Wang

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

1 Citation (Scopus)

Abstract

An efficient algorithm for solving transversal of n disjoint convex polygons with a total of N vertices was discussed. A set S of n disjoint convex polygons in a plane, each with k_i vertices was considered. The transversal problem was to determine whether there exists a straight line that goes through every polygon in S. Results showed that this transversal problem can be solved in O(N + nlogn) time.

Original language	English
Pages (from-to)	141-144
Number of pages	4
Journal	Information Processing Letters
Volume	83
Issue number	3
DOIs	https://doi.org/10.1016/S0020-0190(01)00322-2
Publication status	Published - 16 Aug 2002
Externally published	Yes

Keywords

Computational geometry
Disjoint convex polygon
Stabber
Transversal

Access to Document

10.1016/S0020-0190(01)00322-2

Cite this

@article{618fa6c81e3f45c79066ec851430a901,

title = "Efficient algorithm for transversal of disjoint convex polygons",

abstract = "An efficient algorithm for solving transversal of n disjoint convex polygons with a total of N vertices was discussed. A set S of n disjoint convex polygons in a plane, each with ki vertices was considered. The transversal problem was to determine whether there exists a straight line that goes through every polygon in S. Results showed that this transversal problem can be solved in O(N + nlogn) time.",

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

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

year = "2002",

month = aug,

day = "16",

doi = "10.1016/S0020-0190(01)00322-2",

language = "English",

volume = "83",

pages = "141--144",

number = "3",

}

TY - JOUR

T1 - Efficient algorithm for transversal of disjoint convex polygons

AU - Chin, Francis Y.L.

AU - Wang, Fu Lee

PY - 2002/8/16

Y1 - 2002/8/16

N2 - An efficient algorithm for solving transversal of n disjoint convex polygons with a total of N vertices was discussed. A set S of n disjoint convex polygons in a plane, each with ki vertices was considered. The transversal problem was to determine whether there exists a straight line that goes through every polygon in S. Results showed that this transversal problem can be solved in O(N + nlogn) time.

AB - An efficient algorithm for solving transversal of n disjoint convex polygons with a total of N vertices was discussed. A set S of n disjoint convex polygons in a plane, each with ki vertices was considered. The transversal problem was to determine whether there exists a straight line that goes through every polygon in S. Results showed that this transversal problem can be solved in O(N + nlogn) time.

KW - Computational geometry

KW - Disjoint convex polygon

KW - Stabber

KW - Transversal

UR - http://www.scopus.com/inward/record.url?scp=0037119064&partnerID=8YFLogxK

U2 - 10.1016/S0020-0190(01)00322-2

DO - 10.1016/S0020-0190(01)00322-2

M3 - Article

AN - SCOPUS:0037119064

SN - 0020-0190

VL - 83

SP - 141

EP - 144

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Efficient algorithm for transversal of disjoint convex polygons

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this