Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1202.65029
Milenkovic, Victor; Sacks, Elisha
Two approximate Minkowski sum algorithms. (English)
[J] Int. J. Comput. Geom. Appl. 20, No. 4, 485-509 (2010). ISSN 0218-1959

Authors' abstract: The authors 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 their 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. They 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.
[Francisco Pérez Acosta (La Laguna)]

MSC 2000:: *65D18 Computer graphics and computational geometry

Keywords: Minkowski sum; kinetic framework; robust computational geometry

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]