Transversal of disjoint convex polygons

Chin, F.; Shen, H.; Wang, F.

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

Transversal of disjoint convex polygons

Date

2003

Authors

Chin, F.

Shen, H.

Wang, F.

Type:

Journal article

Citation

Information Processing Letters, 2003; 85(1):55-60

Statement of Responsibility

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

DOI

10.1016/S0020-0190(02)00414-3

Abstract

Given a set S of n disjoint convex polygons {Pi1in} in a plane, each with ki vertices, the transversal problem is to find, if there exists one, a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N+nlogn) time, where N=∑i=1nki is the total number of vertices of the polygons.

Rights

Published Version

https://doi.org/10.1016/s0020-0190(02)00414-3

Persistent link to this record

http://hdl.handle.net/2440/36757

Full item page

Transversal of disjoint convex polygons

Date

Authors

Editors

Advisors

Journal Title

Journal ISSN

Volume Title

Type:

Citation

Statement of Responsibility

Conference Name

DOI

Abstract

School/Discipline

Dissertation Note

Provenance

Description

Access Status

Rights

License

Grant ID

Published Version

Call number

Persistent link to this record