Fat Triangles Determine Linearly Many Holes

DOI10.1137/S009753979018330XMaRDI QIDQ4286234zbMATH OpenOpenAlexWikidataFDO

Authors János Pach, Jiří Matoušek, Micha Sharir, Shmuel Sifrony, Emo Welzl

Publication date 27 April 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979018330x

zbMATH Keywords

combinatorial geometrycomputational geometryDavenport Schinzel sequencesfat trianglesunion of geometric figures

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Convex sets in (2) dimensions (including convex curves) (52A10) Other problems of combinatorial convexity (52A37) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the Boundary Complexity of the Union of Fat Triangles
• Improved bound for the union of fat triangles
• On fat partitioning, fat covering and the union size of polygons
• How many potatoes are in a mesh?
• On fat partitioning, fat covering and the union size of polygons

Cited in

(40)

• Efficient hidden surface removal for objects with small union size
• Point location in fat subdivisions
• Spheres, molecules, and hidden surface removal
• On the union of fat wedges and separating a collection of segments by a line
• Range searching in low-density environments
• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• On fat partitioning, fat covering and the union size of polygons
• Speeding up the incremental construction of the union of geometric objects in practice.
• Models and motion planning
• The complexity of the free space for motion planning amidst fat obstacles
• On the flatness of Minkowski sums
• An optimal algorithm for reporting visible rectangles
• On a class of \(O(n^ 2)\) problems in computational geometry
• Computing depth orders for fat objects and related problems
• Approximate unions of lines and Minkowski sums
• Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
• On the Boundary Complexity of the Union of Fat Triangles
• On a class of O(n^2) problems in computational geometry
• Tangencies between families of disjoint regions in the plane
• Unions of fat convex polytopes have short skeletons
• Geometric Packing under Nonuniform Constraints
• Approximating the k-Level in Three-Dimensional Plane Arrangements
• REACHING A POLYGON WITH DIRECTIONAL UNCERTAINTY
• Models and motion planning
• On the number of regular vertices of the union of Jordan regions
• Computing depth orders and related problems
• Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
• Decomposition of Multiple Packings with Subquadratic Union Complexity
• Improved bound for the union of fat triangles
• On the number of regular vertices of the union of Jordan regions
• Exact and approximation algorithms for computing optimal fat decompositions
• Three dimensional weak visibility: Complexity and applications
• Linear size binary space partitions for fat objects
• Piercing pairwise intersecting convex shapes in the plane
• On the union of cylinders in three dimensions
• Fat triangles inscribed in arbitrary planar domains
• A note on the perimeter of fat objects
• A combinatorial proof of universal optimality for computing a planar convex hull
• On realistic terrains
• Improved bounds on the union complexity of fat objects

This page was built for publication: Fat Triangles Determine Linearly Many Holes

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