DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# 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

# 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

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#