Capturing crossings: Convex hulls of segment and plane intersections

Esther M. Arkin; Joseph S.B. Mitchell; Jack Snoeyink

doi:10.1016/j.ipl.2008.03.024

Capturing crossings: Convex hulls of segment and plane intersections

Applied Mathematics and Statistics

University of North Carolina at Chapel Hill

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

1 Scopus citations

Abstract

We give a simple O (n log n) algorithm to compute the convex hull of the (possibly Θ (n²)) 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 Θ (n^{d - 1}) intersection points on the convex hull.

Original language	English
Pages (from-to)	194-197
Number of pages	4
Journal	Information Processing Letters
Volume	107
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2008.03.024
State	Published - Aug 16 2008

Keywords

Analysis of algorithms
Computational geometry

Access to Document

10.1016/j.ipl.2008.03.024

Cite this

@article{5e3ca93992ed46798895d704ae2ac2b8,

title = "Capturing crossings: Convex hulls of segment and plane intersections",

abstract = "We give a simple O (n log n) 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.",

keywords = "Analysis of algorithms, Computational geometry",

author = "Arkin, \{Esther M.\} and Mitchell, \{Joseph S.B.\} and Jack Snoeyink",

year = "2008",

month = aug,

day = "16",

doi = "10.1016/j.ipl.2008.03.024",

language = "English",

volume = "107",

pages = "194--197",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "5",

}

TY - JOUR

T1 - Capturing crossings

T2 - Convex hulls of segment and plane intersections

AU - Arkin, Esther M.

AU - Mitchell, Joseph S.B.

AU - Snoeyink, Jack

PY - 2008/8/16

Y1 - 2008/8/16

N2 - We give a simple O (n log n) 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.

AB - We give a simple O (n log n) 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.

KW - Analysis of algorithms

KW - Computational geometry

UR - https://www.scopus.com/pages/publications/47149101301

U2 - 10.1016/j.ipl.2008.03.024

DO - 10.1016/j.ipl.2008.03.024

M3 - Article

AN - SCOPUS:47149101301

SN - 0020-0190

VL - 107

SP - 194

EP - 197

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Capturing crossings: Convex hulls of segment and plane intersections

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this