Fast detection of polyhedral intersections

David P. Dobkin; David G. Kirkpatrick

doi:10.1007/BFb0012765

Fast detection of polyhedral intersections

David P. Dobkin, David G. Kirkpatrick

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

24 Scopus citations

Abstract

Methods are given for unifying and extending previous work on detecting polyhedral intersections. The technique of dynamic (vs. static) description is introduced and used to extend previous results. 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)
Title of host publication	Automata, Languages and Programming - 9th Colloquium
Editors	Mogens Nielsen, Erik Meineche Schmidt
Publisher	Springer Verlag
Pages	154-165
Number of pages	12
ISBN (Print)	9783540115762
DOIs	https://doi.org/10.1007/BFb0012765
State	Published - 1982
Event	9th International Colloquium on Automata, Languages and Programming, ICALP 1982 - Aarhus, Denmark Duration: Jul 12 1982 → Jul 16 1982

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	140 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	9th International Colloquium on Automata, Languages and Programming, ICALP 1982
Country/Territory	Denmark
City	Aarhus
Period	7/12/82 → 7/16/82

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/BFb0012765

Cite this

Dobkin, D. P., & Kirkpatrick, D. G. (1982). Fast detection of polyhedral intersections. In M. Nielsen, & E. M. Schmidt (Eds.), Automata, Languages and Programming - 9th Colloquium (pp. 154-165). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 140 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0012765

@inproceedings{77b629d546d64747a16bdaffea930d1b,

title = "Fast detection of polyhedral intersections",

abstract = "Methods are given for unifying and extending previous work on detecting polyhedral intersections. The technique of dynamic (vs. static) description is introduced and used to extend previous results. New upper bounds of O(log n) and O(log2n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.",

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

note = "Publisher Copyright: {\textcopyright} by Springer-Verlag Berlin Heidelberg 1982.; 9th International Colloquium on Automata, Languages and Programming, ICALP 1982 ; Conference date: 12-07-1982 Through 16-07-1982",

year = "1982",

doi = "10.1007/BFb0012765",

language = "English (US)",

isbn = "9783540115762",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "154--165",

editor = "Mogens Nielsen and Schmidt, {Erik Meineche}",

booktitle = "Automata, Languages and Programming - 9th Colloquium",

address = "Germany",

}

Dobkin, DP & Kirkpatrick, DG 1982, Fast detection of polyhedral intersections. in M Nielsen & EM Schmidt (eds), Automata, Languages and Programming - 9th Colloquium. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 140 LNCS, Springer Verlag, pp. 154-165, 9th International Colloquium on Automata, Languages and Programming, ICALP 1982, Aarhus, Denmark, 7/12/82. https://doi.org/10.1007/BFb0012765

Fast detection of polyhedral intersections. / Dobkin, David P.; Kirkpatrick, David G.
Automata, Languages and Programming - 9th Colloquium. ed. / Mogens Nielsen; Erik Meineche Schmidt. Springer Verlag, 1982. p. 154-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 140 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fast detection of polyhedral intersections

AU - Dobkin, David P.

AU - Kirkpatrick, David G.

N1 - Publisher Copyright: © by Springer-Verlag Berlin Heidelberg 1982.

PY - 1982

Y1 - 1982

N2 - Methods are given for unifying and extending previous work on detecting polyhedral intersections. The technique of dynamic (vs. static) description is introduced and used to extend previous results. New upper bounds of O(log n) and O(log2n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.

AB - Methods are given for unifying and extending previous work on detecting polyhedral intersections. The technique of dynamic (vs. static) description is introduced and used to extend previous results. New upper bounds of O(log n) and O(log2n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.

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

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

U2 - 10.1007/BFb0012765

DO - 10.1007/BFb0012765

M3 - Conference contribution

AN - SCOPUS:85037037823

SN - 9783540115762

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 154

EP - 165

BT - Automata, Languages and Programming - 9th Colloquium

A2 - Nielsen, Mogens

A2 - Schmidt, Erik Meineche

PB - Springer Verlag

T2 - 9th International Colloquium on Automata, Languages and Programming, ICALP 1982

Y2 - 12 July 1982 through 16 July 1982

ER -

Fast detection of polyhedral intersections

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this