A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions

Timothy M. Chan

doi:10.1007/s00454-016-9785-3

A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions

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

Abstract

Chazelle [SIAM J Comput 21(4):671–696, 1992] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.

Original language	English (US)
Pages (from-to)	860-865
Number of pages	6
Journal	Discrete and Computational Geometry
Volume	56
Issue number	4
DOIs	https://doi.org/10.1007/s00454-016-9785-3
State	Published - Dec 1 2016
Externally published	Yes

Keywords

Convex polyhedra
Dobkin–Kirkpatrick hierarchy
Intersection

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1007/s00454-016-9785-3

Library availability

Discover UIUC Full Text

Cite this

@article{76fd193e552a4c14a9d08f75a633a4ff,

title = "A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions",

abstract = "Chazelle [SIAM J Comput 21(4):671–696, 1992] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.",

keywords = "Convex polyhedra, Dobkin–Kirkpatrick hierarchy, Intersection",

author = "Chan, {Timothy M.}",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2016",

month = dec,

day = "1",

doi = "10.1007/s00454-016-9785-3",

language = "English (US)",

volume = "56",

pages = "860--865",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions

AU - Chan, Timothy M.

PY - 2016/12/1

Y1 - 2016/12/1

N2 - Chazelle [SIAM J Comput 21(4):671–696, 1992] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.

AB - Chazelle [SIAM J Comput 21(4):671–696, 1992] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.

KW - Convex polyhedra

KW - Dobkin–Kirkpatrick hierarchy

KW - Intersection

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

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

U2 - 10.1007/s00454-016-9785-3

DO - 10.1007/s00454-016-9785-3

M3 - Article

AN - SCOPUS:84964556032

SN - 0179-5376

VL - 56

SP - 860

EP - 865

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this