AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
- 1 September 1996
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 6 (3) , 247-261
- https://doi.org/10.1142/s0218195996000186
Abstract
This paper gives an optimal O(n log n+nk) time algorithm for constructing the levels 1,…, k in an arrangement of n lines in the plane. This algorithm is extended to compute these levels in an arrangement of n unbounded x-monotone polygonal convex chains, of which each pair intersects at most a constant number of times. We then show how these results can be used to solve several geometric optimization problems including the weak separation problem for sets of red and blue points or polygons, the maximum line transversal problem for sets of line segments, the densest hemisphere problem for sets of points on a sphere and the optimal corridor problem for sets of points in the plane. All of the algorithms are quality-sensitive; they run faster if the optimal solution is a good one.Keywords
This publication has 0 references indexed in Scilit: