Approximate unions of lines and Minkowski sums

DOI10.1007/S00453-005-1191-9MaRDI QIDQ2369877zbMATH OpenOpenAlexFDO

Authors Marc Van Kreveld, A. Frank van der Stappen

Publication date 21 June 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/17989

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Algorithms – ESA 2004
• Minkowski sums of projections of convex bodies
• Minkowski sums of point sets defined by inequalities
• Unions of hyperplanes, unions of spheres, and some related estimates
• scientific article; zbMATH DE number 5666383
• On Minkowski sums of simplices
• Approximate convex intersection detection with applications to width and Minkowski sums
• Covering Minkowski sum boundary using points with applications
• Unions of lines in Rn$\mathbb {R}^n$

Cites work

• scientific article; zbMATH DE number 1979490 (Why is no real title available?)
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Computing closely matching upper and lower bounds on textile nesting problems
• Dynamic data structures for fat objects and their applications
• Fat Triangles Determine Linearly Many Holes
• Local polyhedra and geometric graphs
• Multiple translational containment. I: An approximate algorithm
• Multiple translational containment. II: Exact algorithms
• On a class of \(O(n^ 2)\) problems in computational geometry
• On fat partitioning, fat covering and the union size of polygons
• On the Boundary Complexity of the Union of Fat Triangles
• On the boundary of the union of planar convex sets
• On the complexity of the union of fat convex objects in the plane
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• On the union of fat wedges and separating a collection of segments by a line
• Range Searching and Point Location among Fat Objects
• Sharp quantum versus classical query complexity separations
• The complexity of the free space for motion planning amidst fat obstacles
• Triangulating a simple polygon in linear time

Cited in

(4)

• Algorithms – ESA 2004
• Efficient maintenance of the union of intervals on a line, with applications
• Union of random Minkowski sums and network vulnerability analysis
• Two approximate Minkowski sum algorithms

This page was built for publication: Approximate unions of lines and Minkowski sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369877)