Partitioning arrangements of lines. II: Applications (Q921915)

The paper gives interesting results about deterministic algorithms for partitioning arrangements of lines and its applications. It is an extended version of a paper contained in the proceedings of the fifth ACM-Symposium on computational geometry by the same author (Saarbrücken 1989). Many of the applications, which are only listed in that paper, are given here with complete proofs. Such applications are for instance batched implicit point location, batched versions of the polygon containment problem and the implicit hidden surface removal, approximate half-plane range searching, space-query-time tradeoffs in triangle range search and other topics.