In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) an
O(
m
2/3
n
2/3 · log
2/3
n · log
/3 (
m/
n)+(
m+
n) log
n) algorithm to compute all incidences between
m points and
n lines, where is a constant <3.33; (ii) an
O(
m
2/3
n
2/3 · log
5/3
n · log
/3 (
m/
n)+(
m+
n) log
n) algorithm to compute
m faces in an arrangement of
n lines; (iii) an
O(
n
4/3 log
(+2)/3
n) algorithm to count the number of intersections in a set of
n segments; (iv) an
O(
n
4/3 log
( + 2)/3
n) algorithm to count red-blue intersections between two sets of segments, and (v) an
O(
n
3/2 log
/3
n) algorithm to compute spanning trees with low stabbing number for a set of
n points. We also present an algorithm that, given set of
n points in the plane, preprocesses it, in time
O(
nm log
+1/2
n), into a data structure of size
O(
m) for
n log
nmn
2, so that the number of points of
S lying inside a query triangle can be computed in
O((
n/
m) log
3/2
n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in the
Proceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.
相似文献