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:

## ADA210104

# Title:

## Placing the Largest Similar Copy of a Convex Polygon Among Polygonal Obstacles

# Descriptive Note:

## Technical rept.

# Corporate Author:

## CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

# Report Date:

## 1989-01-01

# Pagination or Media Count:

##
21.0

# Abstract:

## Given a convex polygon P and an environment consisting of polygonal obstacles, we find the largest similar copy of P that does not intersect any of the obstacles. Allowing translation, rotation, and change-of-size, our method combines a new notion of Delaunay triangulation for points and edges with the well-known functions based on Davenport-Schinzel sequences producing an almost quadratic algorithm for the problem. Namely, if P is a convex k-gon and if Q has n corners and edges then we can find the placement of the largest similar copy of P in the environment Q in time O k to the 4th power n lambda sub 4 kn log n, where lambda sub 4 is one of the almost-linear functions related to Davenport-Schinzel sequences. If the environment consists only of points then we can find the placement of the largest similar copy of P in time O k-sqn lambda sub 3 kn log n.

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#