Scanline algorithms on a grid

DOI10.1007/BF01934088zbMath0657.68036OpenAlexW2091082218MaRDI QIDQ1111020

Rolf G. Karlsson, Mark H. Overmars

Publication date: 1988

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01934088

zbMATH Keywords

gridsdata structurescomputational geometryrectangular geometry

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to geometry (51-04)

Related Items

Geometric separability using orthogonal objects ⋮ On building the transitive reduction of a two-dimensional poset ⋮ Computing minimum-area rectilinear convex hull and \(L\)-shape ⋮ Ranking intervals under visibility constraints^∗ ⋮ A fast and efficient algorithm for determining the connected orthogonal convex hulls ⋮ Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations ⋮ A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set ⋮ The weighted maximum independent set problem in permutation graphs ⋮ Parallel algorithms for permutation graphs ⋮ A new algorithm for rectangle enclosure reporting

Cites Work

• Unnamed Item
• Upper bounds for sorting integers on random access machines
• Scattering of Rayleigh-Lamb waves from a 2d-cavity in an elastic plate
• New trie data structures which support very fast search operations
• Preserving order in a forest in less than logarithmic time and linear space
• Log-logarithmic worst-case range queries are possible in space theta(N)
• On the identification of the convex hull of a finite set of points in the plane
• Algorithms for Reporting and Counting Geometric Intersections
• A new approach to rectangle intersections
• A priority queue in which initialization and queue operations takeO(loglogD) time
• An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
• Efficient data structures for range searching on a grid
• On Finding the Maxima of a Set of Vectors

This page was built for publication: Scanline algorithms on a grid