TWO APPROXIMATE MINKOWSKI SUM ALGORITHMS
| Autor: | Elisha Sacks, Victor Milenkovic |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Floating point Applied Mathematics Perturbation (astronomy) Monotonic function Kinetic energy Minkowski addition Theoretical Computer Science Computational Mathematics Planar Computational Theory and Mathematics Iterated function Bounded function Geometry and Topology Algorithm Mathematics |
| Zdroj: | International Journal of Computational Geometry & Applications. 20:485-509 |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s0218195910003402 |
| Popis: | We present two approximate Minkowski sum algorithms for planar regions bounded by line and circle segments. Both algorithms form a convolution curve, construct its arrangement, and use winding numbers to identify sum cells. The first uses the kinetic convolution and the second uses our monotonic convolution. The asymptotic running times of the exact algorithms are increased by km log m with m the number of segments in the convolution and k the number of segment triples that are in cyclic vertical order due to approximate segment intersection. The approximate Minkowski sum is close to the exact sum of perturbation regions that are close to the input regions. We validate both algorithms on part packing tasks with industrial part shapes. The accuracy is near the floating point accuracy even after multiple iterated sums. The programs are 2% slower than direct floating point implementations of the exact algorithms. The monotonic algorithm is 42% faster than the kinetic algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|