Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Placing the Largest Similar Copy of a Convex Polygon Among Polygonal Obstacles

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

File(s)
89-964.ps (453.96 KB)
89-964.pdf (1.44 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6880
Collections
Computer Science Technical Reports
Author
Chew, L. Paul
Kedem, Klara
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^{4}n \lambda_{4}(kn)$ log$n$), where \lambda_{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^{2}n \lambda_{3}(kn)$ log $n$).

Date Issued
1989-01
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-964
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance