Loading...
Please wait, while we are loading the content...
Similar Documents
Extremal polygon containment problems (1991).
| Content Provider | CiteSeerX |
|---|---|
| Author | Toledo, Sivan |
| Abstract | Given a convex polygonal object P and an environment consisting of polygonal obstacles, we seek a placement for the largest copy of P that does not intersect any of the obstacles, allowing translation, rotation and scaling. We employ the parametric search technique of Megiddo [Me], and the fixed size polygon placement algorithms developed by Leven and Sharir [LS, LS1], to obtain an algorithm that runs in time O(k 2 n# 4 (kn) log 3 (kn) log log(kn)). We also present several other e#cient algorithms for restricted variants of the extremal polygon containment problem, using the same ideas. These variants include: placement of the largest homothetic copies of one or two convex polygons in another convex polygon and placement of the largest similar copy of a triangle in a convex polygon. 1 Introduction Let P be a convex polygon having k vertices and edges, and let Q be a closed two dimensional space bounded by a collection of polygonal obstacles (the "environment") having altogether n... |
| File Format | |
| Publisher Date | 1991-01-01 |
| Access Restriction | Open |
| Subject Keyword | Extremal Polygon Containment Problem Convex Polygon Polygonal Obstacle Homothetic Copy Sharir L Convex Polygonal Object Log Log Dimensional Space Restricted Variant Parametric Search Technique Similar Copy Introduction Let Present Several Cient Algorithm Environment Consisting Fixed Size Polygon Placement Algorithm |
| Content Type | Text |
