Capturing crossings: Convex hulls of segment and plane intersections

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

Capturing crossings: Convex hulls of segment and plane intersections

Applied Mathematics and Statistics

University of North Carolina at Chapel Hill

Research output: Contribution to conference › Paper › peer-review

Abstract

We give a simple O(nlogn) 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 planes in d-dimensions whose arrangement has Θ(n^d-1) intersection points on the convex hull.

Original language	English
Pages	9-11
Number of pages	3
State	Published - 2007
Event	19th Annual Canadian Conference on Computational Geometry, CCCG 2007 - Ottawa, ON, Canada Duration: Aug 20 2007 → Aug 22 2007

Conference

Conference	19th Annual Canadian Conference on Computational Geometry, CCCG 2007
Country/Territory	Canada
City	Ottawa, ON
Period	08/20/07 → 08/22/07

Cite this

@conference{b920e1cbabd04e398d3f8763756148b5,

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

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 planes in d-dimensions whose arrangement has Θ(nd-1) intersection points on the convex hull.",

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

year = "2007",

language = "English",

pages = "9--11",

note = "19th Annual Canadian Conference on Computational Geometry, CCCG 2007 ; Conference date: 20-08-2007 Through 22-08-2007",

}

TY - CONF

T1 - Capturing crossings

T2 - 19th Annual Canadian Conference on Computational Geometry, CCCG 2007

AU - Arkin, Esther M.

AU - Mitchell, Joseph S.B.

AU - Snoeyink, Jack

PY - 2007

Y1 - 2007

N2 - 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 planes in d-dimensions whose arrangement has Θ(nd-1) intersection points on the convex hull.

AB - 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 planes in d-dimensions whose arrangement has Θ(nd-1) intersection points on the convex hull.

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

M3 - Paper

AN - SCOPUS:84893390060

SP - 9

EP - 11

Y2 - 20 August 2007 through 22 August 2007

ER -

Capturing crossings: Convex hulls of segment and plane intersections

Abstract

Conference

Other files and links

Fingerprint

Cite this