A new technique for analyzing substructures in arrangements of piecewise linear surfaces

No abstract is available for this paper.

• Publication year

  1996

• Venue

  Discrete & Computational Geometry

• Publication date

  1996-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BF02712877
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

  2011cited by this paper
• Vertical decomposition of arrangements of hyperplanes in four dimensions

  1995cited by this paper
• Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

  1995cited by this paper
• Arrangements and their applications in robotics: recent developments

  1995cited by this paper
• Davenport-Schinzel sequences and their geometric applications

  1995influential reference
• The overlay of lower envelopes in three dimensions and its applications

  1995cited by this paper
• On lazy randomized incremental construction

  1994influential reference
• On translational motion planning in three dimensions

  1994cited by this paper
• Vertical decompositions for triangles in 3-space

  1994influential reference
• Almost tight upper bounds for lower envelopes in higher dimensions

  1993cited by this paper
• Computational geometry - an introduction through randomized algorithms

  1993cited by this paper
• New bounds for lower envelopes in three dimensions, with applications to visibility in terrains

  1993cited by this paper
• The union of convex polyhedra in three dimensions

  1993cited by this paper
• Combinatorics and Algorithms of Arrangements

  1993cited by this paper
• Castles in the air revisited

  1992influential reference
• Counting facets and incidences

  1992influential reference
• On the Zone Theorem for Hyperplane Arrangements

  1991cited by this paper
• On the zone of a surface in a hyperplane arrangement

  1991cited by this paper
• Triangles in space or building (and analyzing) castles in the air

  1990cited by this paper
• The upper envelope of piecewise linear functions: Tight bounds on the number of faces

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

  1988influential reference
• Applications of random sampling in computational geometry, II

  1988cited by this paper
• Algorithms in Combinatorial Geometry

  1987cited by this paper
• New applications of random sampling in computational geometry

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

  1986cited by this paper
• Geometry © 1996 Springer-Verlag New York Inc. The Overlay of Lower Envelopes and Its Applications ∗

  year unknowncited by this paper

• Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

  2025cites this paper
• Lower Envelopes of Surface Patches in 3-Space

  2024cites this paper
• Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D

  2023cites this paper
• An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems

  2021cites this paper
• Stronger bounds for weak epsilon-nets in higher dimensions

  2021cites this paper
• 28 Arrangements

  2016cites this paper
• 44 RANDOMIZATION AND DERANDOMIZATION

  2016cites this paper
• On the Zarankiewicz problem for intersection hypergraphs

  2015cites this paper
• Epsilon-Nets for Halfspaces Revisited

  2014cites this paper
• Epsilon-Nets for Halfspaces Revisited

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

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

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

  2010cites this paper
• Improved Bounds for Geometric Permutations

  2010influential citation
• On Regular Vertices of the Union of Planar Convex Objects

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

  2008cites this paper
• Geometric Arrangements: Substructures and Algorithms

  2007cites this paper
• On regular vertices on the union of planar objects

  2007cites this paper
• A Single Cell in an Arrangement of Convex Polyhedra in ${\Bbb R}^3$

  2007influential citation
• State of the Union ( of Geometric Objects ) : A Review ∗

  2007cites this paper
• Geometric arrangements: substructures and algorithms

  2007cites this paper
• Visibility maps of segments and triangles in 3D

  2006cites this paper
• On a Single Cell in an Arrangement of Convex Polyhedra in R 3 ∗

  2006influential citation
• Combinatorial Geometry with Algorithmic Applications

  2006influential citation
• Almost tight bound for a single cell in an arrangement of convex polyhedra in R3

  2005influential citation
• Sharp Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions

  2004cites this paper
• Matching Polyhedral Terrains Using Overlays of Envelopes

  2004influential citation
• Output-sensitive construction of the union of triangles

  2004cites this paper
• On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences

  2003cites this paper
• A lower bound on Voronoi diagram complexity

  2002cites this paper
• Improved construction of vertical decompositions of three-dimensional arrangements

  2002influential citation
• The partition technique for overlays of envelopes

  2002cites this paper
• Polyhedral Voronoi Diagrams of Polyhedra in Three Dimensions

  2002cites this paper
• Almost tight upper bounds for vertical decompositions in four dimensions

  2001influential citation
• Complexity Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions

  2001influential citation
• A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

  2001influential citation
• Arrangements and Their Applications

  2000cites this paper
• Recent Developments in the Theory of Arrangements of Surfaces

  1999cites this paper
• On the combinatorial and topological complexity of a single cell

  1998cites this paper
• The Combinatorial and Topological Complexity of a Single Cell

  1998cites this paper
• Dynamic motion planning in low obstacle density environments

  1997cites this paper