Fat Triangles Determine Linearly Many Holes

No abstract is available for this paper.

• Publication year

  1994

• Venue

  SIAM journal on computing (Print)

• Publication date

  1994-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/S009753979018330X
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On arrangements of Jordan arcs with three intersections per pair

  2018cited by this paper
• On the general motion-planning problem with two degrees of freedom

  2015cited by this paper
• On the Union of Fat Wedges and Separating a Collection of Segments By a Line

  1993cited by this paper
• Arrangements of curves in the plane

  1992cited by this paper
• A simple output-sensitive algorithm for hidden surface removal

  1992cited by this paper
• Onk-sets in arrangements of curves and surfaces

  1991cited by this paper
• Computing a face in an arrangement of line segments

  1991cited by this paper
• The Intersection Searching Problem for c-Oriented Polygons

  1991cited by this paper
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

  1990cited by this paper
• The complexity and construction of many faces in arrangements of lines and of segments

  1990cited by this paper
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences

  1989cited by this paper
• An optimal algorithm for intersecting line segments in the plane

  1988cited by this paper
• Planar realizations of nonlinear davenport-schinzel sequences by segments

  1988cited by this paper
• Reporting and Counting Intersections Between Two Sets of Line Segments

  1988cited by this paper
• Optimal Computation of Finitely Oriented Convex Hulls

  1987cited by this paper
• Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemes

  1986cited by this paper
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles

  1986cited by this paper
• New algorithms for special cases of the hidden line elimination problem

  1985cited by this paper
• A Fast Algorithm for Polygon Containment by Translation (Extended Abstract)

  1985cited by this paper
• Conquering contours - efficient algorithms for computational geometry

  1983cited by this paper

• A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull

  2025cites this paper
• Regular triangle unions with maximal number of sides

  2025cites this paper
• Fat Triangles Inscribed in Arbitrary Planar Domains

  2023cites this paper
• Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning

  2019cites this paper
• On combinatorial approximation algorithms in geometry

  2018cites this paper
• Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning

  2017cites this paper
• 28 Arrangements

  2016cites this paper
• Approximating the $k$-Level in Three-Dimensional Plane Arrangements

  2016cites this paper
• ALGORITHMIC MOTION PLANNING

  2016cites this paper
• 50 ALGORITHMIC MOTION PLANNING

  2016cites this paper
• Instance Optimal Geometric Algorithms

  2015cites this paper
• A Survey of Computational Geometry

  2014cites this paper
• Improved Bounds for the Union of Locally Fat Objects in the Plane

  2014cites this paper
• Decomposition of Multiple Packings with Subquadratic Union Complexity

  2013cites this paper
• Realistic Analysis for Algorithmic Problems on Geographical Data

  2013cites this paper
• The notions of multiple packings and coverings were introduced in a geometric setting independently

  2013cites this paper
• Pushing and pulling : computing push plans for disk-shaped robots, and dynamic labelings for moving points

  2013cites this paper
• Sharp bounds on Davenport-Schinzel sequences of every order

  2013cites this paper
• Small-Size Relative (p,Epsilon)-Approximations for Well-Behaved Range Spaces

  2012cites this paper
• Commentationes Mathematicae Universitatis Carolinae

  2012cites this paper
• Sharp Bounds on Davenport-Schinzel Sequences of Every Order

  2012cites this paper
• Unions of Fat Convex Polytopes Have Short Skeletons

  2012cites this paper
• On a class of O(n2) problems in computational geometry

  2012cites this paper
• Unions of Fat Convex Polytopes Have Short Skeletons

  2012cites this paper
• Small-size relative (p,ε)-approximations for well-behaved range spaces

  2012cites this paper
• How Many Potatoes Are in a Mesh?

  2012cites this paper
• Covering Problems via Structural Approaches

  2011cites this paper
• Geometric packing under non-uniform constraints

  2011cites this paper
• Depth, crossings and conflicts in discrete geometry

  2011cites this paper
• Range searching: emptiness, reporting, and approximate counting

  2011cites this paper
• On the structure and composition of forbidden sequences, with geometric applications

  2011cites this paper
• Improved Bounds for the Union of Locally Fat Objects in the Plane

  2011cites this paper
• Improved bound for the union of fat triangles

  2011cites this paper
• A note on the perimeter of fat objects

  2011cites this paper
• Tangencies between families of disjoint regions in the plane

  2010cites this paper
• Weighted geometric set cover via quasi-uniform sampling

  2010cites this paper
• On the perimeter of fat objects

  2010cites this paper
• The union of colorful simplices spanned by a colored point set

  2010cites this paper
• Realistic Computer Models

  2010cites this paper
• Better bounds on the union complexity of locally fat objects

  2010cites this paper
• Data Imprecision in Computational Geometry

  2009cites this paper
• Epsilon nets and union complexity

  2009cites this paper
• Instance-Optimal Geometric Algorithms

  2009cites this paper
• Small-size ε-nets for axis-parallel rectangles and boxes

  2009influential citation
• Epsilon Nets and Union Complexity

  2009cites this paper
• Near-Linear Approximation Algorithms for Geometric Hitting Sets

  2009cites this paper
• Semialgebraic Range Reporting and Emptiness Searching with Applications

  2009cites this paper
• A NOTE ON THE PERIMETER OF ( α , β ) – COVERED OBJECTS

  2009cites this paper
• On the union of fat tetrahedra in three dimensions

  2009cites this paper
• State of the Union (of geometric objects)

  2008cites this paper
• On the Union of Cylinders in Three Dimensions

  2008cites this paper
• Geometric arrangements: substructures and algorithms

  2007cites this paper
• Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions

  2007cites this paper
• State of the Union ( of Geometric Objects ) : A Review ∗

  2007cites this paper
• Euclidean Shortest Paths on Polyhedra in Three Dimensions

  2007cites this paper
• Geometric Arrangements: Substructures and Algorithms

  2007cites this paper
• Shortest paths on realistic polyhedra

  2007cites this paper
• Extractors And Rank Extractors For Polynomial Sources

  2007cites this paper
• Euclidean shortest paths on polyhedra in three dimensions

  2007cites this paper
• On the Union of κ-Round Objects in Three and Four Dimensions

  2006cites this paper
• Combinatorial Geometry with Algorithmic Applications

  2006cites this paper
• On realistic terrains

  2006cites this paper
• Improved Bounds on the Union Complexity of Fat Objects

  2005cites this paper
• Vertical ray shooting for fat objects

  2005cites this paper
• The interface between computational and combinatorial geometry

  2005cites this paper
• Improved Approximation Algorithms for Geometric Set Cover

  2005cites this paper
• On approximating the depth and related problems

  2005cites this paper
• Output-sensitive construction of the union of triangles

  2004cites this paper
• On the union of kapa-round objects

  2004cites this paper
• On lines avoiding unit balls in three dimensions

  2004cites this paper
• On the union of κ-round objects

  2004cites this paper
• Approximate unions of lines and minkowski sums

  2004influential citation
• Algorithms for Fat Objects: Decompositions and Applications

  2004cites this paper
• Exact and approximation algorithms for computing optimal fat decompositions

  2004cites this paper
• On the number of intersections of two polygons

  2003cites this paper
• Combinatorial problems in computational geometry

  2003cites this paper
• The Union of Congruent Cubes in Three Dimensions

  2003cites this paper
• Reaching a Polygon with Directional Uncertainty

  2003cites this paper
• Speeding up the incremental construction of the union of geometric objects in practice

  2002cites this paper
• Pseudo-line arrangements: duality, algorithms, and applications

  2002cites this paper
• On the fatness of Minkowski sums

  2002cites this paper
• TSP with Neighborhoods of Varying Size

  2002cites this paper
• An optimal algorithm for reporting visible rectangles

  2002cites this paper
• Realistic Input Models for Geometric Algorithms

  2002cites this paper
• Reaching a Polygon with Directional Uncertainty

  2001cites this paper
• Online Point Location in Planar Arrangements and Its Applications

  2001cites this paper
• Robust Geometric Algorithms for Sensor Planning

  2001cites this paper
• Data Transfer and Interface Propagation in Multicomponent Simulations

  2001cites this paper
• The union of congruent cubes in three dimensions

  2001cites this paper
• Linear Size Binary Space Partitions for Uncluttered Scenes

  2000cites this paper
• On the boundary complexity of the union of fat triangles

  2000cites this paper
• The Complexity of the Union of ( α , β )-Covered Objects ∗

  2000cites this paper
• Visibility-Based Planning of Sensor Control Strategies

  2000cites this paper
• Geometric Eccentricity and the Complexity of Manipulation Plans

  2000cites this paper
• Cutting Glass

  2000cites this paper
• Arrangements and Their Applications

  2000cites this paper
• The 2-center problem with obstacles

  2000cites this paper
• On the Complexity of the Union of Geometric Objects

  2000cites this paper
• On the Complexity of the Union of Fat Convex Objects in the Plane

  2000cites this paper
• Three-dimensional weak visibility: Complexity and applications

  2000cites this paper