On the union of fat wedges and separating a collection of segments by a line

DOI10.1016/0925-7721(93)90018-2MaRDI QIDQ1314526zbMATH OpenOpenAlexFDO

Authors Alon Efrat, Günter Rote, Micha Sharir

Publication date 29 November 1994

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(93)90018-2

zbMATH Keywords

fat trianglesseparator linevisibility graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Separating and shattering long line segments
• Separating and shattering long line segments
• Separating objects in the plane by wedges and strips
• Separating translates in the plane: Combinatorial bounds and an algorithm
• Algorithms for weak and wide separation of sets

Cites work

• A fast planar partition algorithm. I
• An optimal algorithm for intersecting line segments in the plane
• An optimal algorithm for the boundary of a cell in a union of rays
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Applications of random sampling in computational geometry. II
• Better lower bounds on detecting affine and spherical degeneracies
• Fat Triangles Determine Linearly Many Holes
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• The complexity and construction of many faces in arrangements of lines and of segments
• Topologically sweeping an arrangement

Cited in

(19)

• 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
• Shattering a set of objects in 2D
• On the union complexity of families of axis-parallel rectangles with a low packing number
• 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
• Separating and shattering long line segments
• SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
• On a class of O(n^2) problems in computational geometry
• Computing depth orders and related problems
• Locating an obnoxious line among planar objects
• Decomposition of Multiple Packings with Subquadratic Union Complexity
• Separating objects in the plane by wedges and strips
• Linear size binary space partitions for fat objects
• Piercing pairwise intersecting convex shapes in the plane
• Separating and shattering long line segments
• Improved bounds on the union complexity of fat objects

This page was built for publication: On the union of fat wedges and separating a collection of segments by a line

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