| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428778 | Information Processing Letters | 2008 | 4 Pages |
Abstract
We give a simple O(nlogn) algorithm to compute the convex hull of the (possibly Θ(n2)) intersection points in an arrangement of n line segments in the plane. We also show an arrangement of dn hyperplanes in d-dimensions whose arrangement has Θ(nd−1) intersection points on the convex hull.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
