Aligning Two Convex Figures to Minimize Area or Perimeter

Cited 8 time in webofscience Cited 0 time in scopus
  • Hit : 598
  • Download : 0
Given two compact convex sets P and Q in the plane, we consider the problem of finding a placement I center dot P of P that minimizes the convex hull of I center dot Pa(a)Q. We study eight versions of the problem: we consider minimizing either the area or the perimeter of the convex hull; we either allow I center dot P and Q to intersect or we restrict their interiors to remain disjoint; and we either allow reorienting P or require its orientation to be fixed. In the case without reorientations, we achieve exact near-linear time algorithms for all versions of the problem. In the case with reorientations, we compute a (1+epsilon)-approximation in time O(epsilon (-1/2)log n+epsilon (-3/2)log (a) (1/epsilon)) if the two sets are convex polygons with n vertices in total, where aa{0,1,2} depending on the version of the problem.
Publisher
SPRINGER
Issue Date
2012-02
Language
English
Article Type
Article
Keywords

MAXIMUM OVERLAP; POLYGONS; PACKING; TRANSLATIONS; SETS; HULL

Citation

ALGORITHMICA, v.62, pp.464 - 479

ISSN
0178-4617
DOI
10.1007/s00453-010-9466-1
URI
http://hdl.handle.net/10203/100587
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 8 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0