Accession Number:

ADA056889

Title:

Finding the Intersection of Two Convex Polyhedra.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB

Personal Author(s):

• Muller,D. E.
• Preparata,F. P.

Report Date:

1977-10-01

Pagination or Media Count:

38.0

Abstract:

Given two convex polyhedra in three-dimensional space, we develop an algorithm to 1 test whether their intersection is empty, and 2 if so to find a separating plane, while 3 if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in time 0nlogn, where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with 3 constructing the intersection is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point. Author

Descriptors:

• *ALGORITHMS
• PROBLEM SOLVING
• GEOMETRY
• CONVEX SETS
• THEOREMS

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE