Approximate unions of lines and Minkowski sums

DOI10.1007/S00453-005-1191-9zbMATH Open1117.68080OpenAlexW2096226935MaRDI QIDQ2369877FDOQ2369877

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

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$

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)