DC Field | Value | Language |
---|---|---|
dc.contributor.author | AHN, HEE KAP | - |
dc.contributor.author | Siu-Wing Cheng | - |
dc.contributor.author | Iris Reinbacher | - |
dc.date.accessioned | 2016-03-31T08:13:41Z | - |
dc.date.available | 2016-03-31T08:13:41Z | - |
dc.date.created | 2011-03-24 | - |
dc.date.issued | 2010-12 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.other | 2013-OAK-0000029185 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/14840 | - |
dc.description.abstract | We study the problem of maximizing the overlap of two convex polytopes under translation in R-d for some constant d >= 3. Let n be the number of bounding hyperplanes of the polytopes. We present an algorithm that, for any epsilon > 0, finds an overlap at least the optimum minus E and reports the translation realizing it. The running time is 0(n(left perpendiculard/2right perpendicular+1) log(d) n) with probability at least 1 - n(-0(1)), which can be improved to 0(n log(3.5)n) in R-3. The time complexity analysis depends on a bounded incidence condition that we enforce with probability one by randomly perturbing the input polytopes. The perturbation causes an additive error epsilon, which can be made arbitrarily small by decreasing the perturbation magnitude. Our algorithm in fact computes the maximum overlap of the perturbed polytopes. The running time bounds, the probability bound, and the big-O constants in these bounds are independent of epsilon. (C) 2011 Elsevier B.V. All rights reserved. | - |
dc.description.statementofresponsibility | X | - |
dc.language | English | - |
dc.publisher | Springer | - |
dc.relation.isPartOf | Lecture Notes in Computer Science | - |
dc.title | Maximum Overlap of Convex Polytopes under Translation | - |
dc.type | Article | - |
dc.contributor.college | 컴퓨터공학과 | - |
dc.identifier.doi | 10.1007/978-3-642-17514-5_9 | - |
dc.author.google | Ahn, HK | - |
dc.author.google | Cheng, SW | - |
dc.author.google | Reinbacher, I | - |
dc.relation.volume | 46 | - |
dc.relation.issue | 5 | - |
dc.relation.startpage | 552 | - |
dc.relation.lastpage | 565 | - |
dc.contributor.id | 10152366 | - |
dc.relation.journal | Computational Geometry | - |
dc.relation.index | SCI급, SCOPUS 등재논문 | - |
dc.relation.sci | SCI | - |
dc.collections.name | Journal Papers | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | Lecture Notes in Computer Science, v.6507, no.2, pp.97 - 108 | - |
dc.identifier.wosid | 000296483600009 | - |
dc.date.tcdate | 2019-01-01 | - |
dc.citation.endPage | 108 | - |
dc.citation.number | 2 | - |
dc.citation.startPage | 97 | - |
dc.citation.title | Lecture Notes in Computer Science | - |
dc.citation.volume | 6507 | - |
dc.contributor.affiliatedAuthor | AHN, HEE KAP | - |
dc.identifier.scopusid | 2-s2.0-78650899912 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 1 | - |
dc.description.isOpenAccess | N | - |
dc.type.docType | CONFERENCE PAPER | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.