Overlap of convex polytopes under rigid motion
| Autor: | Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, Juyoung Yon |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
000 Computer science
knowledge general works Control and Optimization Regular polygon Approximation algorithm Polytope Computer Science Applications Combinatorics Computational Mathematics Computational Theory and Mathematics Intersection Computer Science Convex polytope Shape matching Rigid motion Physics::Atomic Physics Geometry and Topology Constant (mathematics) Mathematics |
| Zdroj: | Computational Geometry. 47:15-24 |
| ISSN: | 0925-7721 |
| Popis: | We present an algorithm to compute a rigid motion that approximately maximizes the volume of the intersection of two convex polytopes P"1 and P"2 in R^3. For all @e@?(0,1/2] and for all n>=1/@e, our algorithm runs in O(@e^-^3nlog^3^.^5n) time with probability 1-n^-^O^(^1^). The volume of the intersection guaranteed by the output rigid motion is a (1-@e)-approximation of the optimum, provided that the optimum is at least @l@?max{|P"1|,|P"2|} for some given constant @l@?(0,1]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect