Stacking and bundling two convex polygons

Given two compact convex sets C-1 and C-2 in the plane, we consider the problem of finding a placement phi C-1 of C-1 that minimizes the area of the convex hull of phi C-1 boolean OR C-2. We first consider the case where phi C-1 and C-2 are allowed to intersect (as in "stacking" two flat objects in a convex box), and then add the restriction that their interior has to remain disjoint (as when "bundling" two convex objects together into a tight bundle). In both cases, we consider both the case where we are allowed to reorient C-1, and where the orientation is fixed. In the case without reorientations, we achieve exact near-linear time algorithms, in the case with reorientations we compute a (1 + epsilon)-approximation in time O(epsilon(-1/2) log n+epsilon(-3/2) log epsilon(-1/2)), if two sets are convex polygons with n vertices in total.
Publisher
SPRINGER-VERLAG BERLIN
Issue Date
2005
Language
ENG
Keywords

OVERLAP

Citation

ALGORITHMS AND COMPUTATION BOOK SERIES: LECTURE NOTES IN COMPUTER SCIENCE, v.3827, pp.882 - 891

ISSN
0302-9743
URI
http://hdl.handle.net/10203/87371
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 116
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 1 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0