On fat partitioning, fat covering and the union size of polygons

DOI10.1016/S0925-7721(96)00016-8zbMath0894.68155OpenAlexW2141110561MaRDI QIDQ1384209

Marc J. van Kreveld

Publication date: 7 September 1998

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(96)00016-8

zbMATH Keywords

computational geometryfat trianglesfat simple polygon

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (12)

Generalized disk graphs ⋮ Approximate unions of lines and Minkowski sums ⋮ An optimal-time algorithm for shortest paths on realistic polyhedra ⋮ Connect the Dot: Computing Feed-Links with Minimum Dilation ⋮ Exact and approximation algorithms for computing optimal fat decompositions ⋮ Piercing pairwise intersecting convex shapes in the plane ⋮ Decomposition of Multiple Packings with Subquadratic Union Complexity ⋮ On realistic terrains ⋮ Improved bounds on the union complexity of fat objects ⋮ Placing Text Boxes on Graphs ⋮ Decompositions and boundary coverings of non-convex fat polyhedra ⋮ On the flatness of Minkowski sums

Cites Work

• Unnamed Item
• Unnamed Item
• Range searching with efficient hierarchical cuttings
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• On \(k\)-sets in arrangements of curves and surfaces
• Hidden surface removal for \(c\)-oriented polyhedra
• Applications of a new space-partitioning technique
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Efficient hidden surface removal for objects with small union size
• Point location in fat subdivisions
• Cutting hyperplanes for divide-and-conquer
• On arrangements of Jordan arcs with three intersections per pair
• On the union of fat wedges and separating a collection of segments by a line
• The complexity of the free space for a robot moving amidst fat obstacles
• Filling polyhedral molds.
• Algorithms for Reporting and Counting Geometric Intersections
• Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
• Generalization of Voronoi Diagrams in the Plane
• Fat Triangles Determine Linearly Many Holes
• On fat partitioning, fat covering and the union size of polygons

This page was built for publication: On fat partitioning, fat covering and the union size of polygons