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

DOI10.1016/0925-7721(93)90018-2zbMath0801.68167MaRDI QIDQ1314526

Günter Rote, Alon Efrat, 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

visibility graph; fat triangles; separator line

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Improved bounds on the union complexity of fat objects, 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 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, SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS

Cites Work

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