DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, HK | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.date.accessioned | 2013-03-06T15:11:40Z | - |
dc.date.available | 2013-03-06T15:11:40Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2005 | - |
dc.identifier.citation | ALGORITHMS AND COMPUTATION BOOK SERIES: LECTURE NOTES IN COMPUTER SCIENCE, v.3827, pp.882 - 891 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10203/87371 | - |
dc.description.abstract | 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. | - |
dc.language | English | - |
dc.publisher | SPRINGER-VERLAG BERLIN | - |
dc.subject | OVERLAP | - |
dc.title | Stacking and bundling two convex polygons | - |
dc.type | Article | - |
dc.identifier.wosid | 000234885900088 | - |
dc.identifier.scopusid | 2-s2.0-33744950437 | - |
dc.type.rims | ART | - |
dc.citation.volume | 3827 | - |
dc.citation.beginningpage | 882 | - |
dc.citation.endingpage | 891 | - |
dc.citation.publicationname | ALGORITHMS AND COMPUTATION BOOK SERIES: LECTURE NOTES IN COMPUTER SCIENCE | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Ahn, HK | - |
dc.type.journalArticle | Article; Proceedings Paper | - |
dc.subject.keywordPlus | OVERLAP | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.