Fast detection of polyhedral intersection

David P. Dobkin; David G. Kirkpatrick

doi:10.1016/0304-3975(82)90120-7

Fast detection of polyhedral intersection

David P. Dobkin, David G. Kirkpatrick

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

130 Scopus citations

Abstract

Methods are given for unifying and extending previous work on detecting intersections of suitably preprocessed polyhedra. New upper bounds of O(log n) and O(log² n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.

Original language	English (US)
Pages (from-to)	241-253
Number of pages	13
Journal	Theoretical Computer Science
Volume	27
Issue number	3
DOIs	https://doi.org/10.1016/0304-3975(82)90120-7
State	Published - 1983

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(82)90120-7

Cite this

@article{0dfa409c04dd4ce18104f63fd4a3f751,

title = "Fast detection of polyhedral intersection",

abstract = "Methods are given for unifying and extending previous work on detecting intersections of suitably preprocessed polyhedra. New upper bounds of O(log n) and O(log2 n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.",

author = "Dobkin, \{David P.\} and Kirkpatrick, \{David G.\}",

year = "1983",

doi = "10.1016/0304-3975(82)90120-7",

language = "English (US)",

volume = "27",

pages = "241--253",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Fast detection of polyhedral intersection

AU - Dobkin, David P.

AU - Kirkpatrick, David G.

PY - 1983

Y1 - 1983

N2 - Methods are given for unifying and extending previous work on detecting intersections of suitably preprocessed polyhedra. New upper bounds of O(log n) and O(log2 n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.

AB - Methods are given for unifying and extending previous work on detecting intersections of suitably preprocessed polyhedra. New upper bounds of O(log n) and O(log2 n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.

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

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

U2 - 10.1016/0304-3975(82)90120-7

DO - 10.1016/0304-3975(82)90120-7

M3 - Article

AN - SCOPUS:0001520324

SN - 0304-3975

VL - 27

SP - 241

EP - 253

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

Fast detection of polyhedral intersection

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this