Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414302 | Computational Geometry | 2014 | 10 Pages |
Abstract
We present an algorithm to compute a rigid motion that approximately maximizes the volume of the intersection of two convex polytopes P1P1 and P2P2 in R3R3. For all ε∈(0,1/2]ε∈(0,1/2] and for all n⩾1/εn⩾1/ε, our algorithm runs in O(ε−3nlog3.5n) time with probability 1−n−O(1)1−n−O(1). The volume of the intersection guaranteed by the output rigid motion is a (1−ε)(1−ε)-approximation of the optimum, provided that the optimum is at least λ⋅max{|P1|,|P2|}λ⋅max{|P1|,|P2|} for some given constant λ∈(0,1]λ∈(0,1].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, Juyoung Yon,