Scanline algorithms on a grid
In computational geometry (the design and analysis of explicit algorithms and data structures representing geometrical objects in Euclidean space) there exists a large collection of problems where the results are determined almost completely by the order relations between coordinates rather than by these coordinates themselves. A typical example is the problem of determining the maximal points in a finite point set under the partial order ``being greater than in both coordinates. This makes it possible to transform the input from a set of points with real coordinates into points with integer coordinates within the range 1...n where n is the number of points; this transformation preserves the structure of the answers. The advantage is that the transformed problem supports the use of clever data structures and algorithms which otherwise would not be applicable. The disadvantage is that the transformation requires the input data to be sorted leading to an additional O(n log(n)) term in the complexity for the algorithms. For many of these problems the complexity is O(n log(n)) anyhow and then the transformation doesn't make sense. If the input however consists of points on a grid rather than points with arbitrary real coordinates there are alternative ways of sorting points and preserving order in a finite set under insertions and deletions, and this opens the road towards the list of improved bounds as presented in the paper. In the list presented on the second page of the paper the general pattern is that factors log(n) are replaced by log log(n) or log \(log_ n(u)\) where u is the ``universe size (number of grid points in one direction). The first replacement indicates that the efficient priority deques as discovered by the reviewer and modified by D. B. Johnson is used in the revised algorithm. The second replacement indicates the use of a sorting method of Kirkpatrick and Reisch. For the last three problems described the new bounds are obtained by more involved methods. The paper also introduces a number of data structures which are interesting by themselves.
- A new approach to rectangle intersections
- A priority queue in which initialization and queue operations takeO(loglogD) time
- Algorithms for Reporting and Counting Geometric Intersections
- An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
- Efficient data structures for range searching on a grid
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- Log-logarithmic worst-case range queries are possible in space theta(N)
- New trie data structures which support very fast search operations
- On Finding the Maxima of a Set of Vectors
- On the identification of the convex hull of a finite set of points in the plane
- Preserving order in a forest in less than logarithmic time and linear space
- Scattering of Rayleigh-Lamb waves from a 2d-cavity in an elastic plate
- Upper bounds for sorting integers on random access machines
- The weighted maximum independent set problem in permutation graphs
- Parallel algorithms for permutation graphs
- A new algorithm for rectangle enclosure reporting
- Geometric separability using orthogonal objects
- A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set
- A fast and efficient algorithm for determining the connected orthogonal convex hulls
- On building the transitive reduction of a two-dimensional poset
- Constant-work-space image scan with a given angle
- Fast raster scan distance propagation on the discrete rectangular lattice
- Ranking intervals under visibility constraints∗
- scientific article; zbMATH DE number 645770 (Why is no real title available?)
- Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations
- Efficient real-time and parallel algorithm for connected orthogonal convex hulls on large point sets
- Computing minimum-area rectilinear convex hull and L-shape
This page was built for publication: Scanline algorithms on a grid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111020)
