Back to search

University of British Columbia

A simple primal algorithm for intersecting 3-polyhedra in linear time

Abstract

dc:description

This thesis presents, in full, a simple linear time algorithm for intersecting two convex 3-polyhedra P and Q. This differs from the first such algorithm — due to Chazelle — in that it operates entirely in primal space, whereas Chazelle's algorithm relies heavily on duality transforms. We use the hierarchical representations of polyhedra due to Dobkin and Kirkpatrick to induce a cell complexes between coarse approximations, Pk and Pk of P satisfying Pk ⊆ P ⊆ Pk, and similar approximations Qk and Qk of Q satisfying Qk ⊆ Q ⊆ Qk . We show that the structure of such complexes allows intersection queries to be answered efficiently. In particular, the sequence of cells intersected by a ray can be identified in time proportional to the length of the sequence. The algorithm operates by recursively computing the intersections: Pk ∩ Qk and Pk ∩Qk. Then edges of the union of approximations P ∩ Qk and Q ∩ Pk are traversed by tracing their intersection with the two cell complexes. We show that each such edge can be traversed in constant time. In the process, most of the edges of P ∩ Q which lie simultaneously on the boundary of P and Q will be traced. We show that the total time needed to construct those which remain is linear in the size of P and Q. Though based on the same general principles, the algorithm presented here is somewhat simpler than that described by Chazelle, which uses only the cell complexes induced by the inner hierarchical representations of P and Q. By extending Chazelle's search structure to the space exterior to the given polyhedra, we avoid having to operate simultaneously in primal and dual spaces. This permits us to conceptualise the algorithm as traversing the edges of the boundary of (P∩Qk)⋃(Q∩Pk). As a side effect, we avoid one half of Chazelle's recursive calls, which leads to a modest improvement in the asymptotic constants.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1991

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Martin, Andrew K.

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/30114

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Martin, Andrew K.. A simple primal algorithm for intersecting 3-polyhedra in linear time. master's thesis, University of British Columbia, 1991. http://hdl.handle.net/2429/30114