# Item

ITEM ACTIONSEXPORT

Released

Report

#### New deterministic algorithms for counting pairs of intersecting segments and off-line triangle range searching

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-95-1-022.pdf

(Any fulltext), 43MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Pellegrini, M.(1995). *New deterministic algorithms for counting
pairs of intersecting segments and off-line triangle range searching* (MPI-I-1995-1-022). Saarbrücken: Max-Planck-Institut
für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A1E9-4

##### Abstract

We describe a new method for decomposing planar sets of segments and
points.
Using this method we obtain
new efficient {\em deterministic}
algorithms for counting pairs of intersecting
segments, and for answering off-line triangle range queries.
In particular we obtain the following results:
\noindent
(1)
Given $n$ segments in the plane, the number $K$ of
pairs of intersecting segments is computed in time
$O(n^{1+\epsilon} + K^{1/3}n^{2/3 + \epsilon})$, where
$\epsilon >0$ an arbitrarily small constant.
\noindent
(2)
Given $n$ segments in the plane which are coloured with two colours,
the number of pairs of {\em bi-chromatic} intersecting segments is
computed in time
$O(n^{1+\epsilon} + K_m^{1/3}n^{2/3 +\epsilon})$, where $K_m$ is the number of {\em
mono-chromatic} intersections, and $\epsilon >0$ is an arbitrarily small constant.
\noindent
(3)
Given $n$ weighted points and $n$ triangles on a plane,
the sum of weights of points in each triangle is computed
in time $O(n^{1+\epsilon} + {\cal K}^{1/3}n^{2/3 +\epsilon})$,
where ${\cal K}$ is the number of vertices in the arrangement of the triangles,
and $\epsilon>0$ an arbitrarily small constant. The above bounds depend sub-linearly on the number of
intersections among segments $K$ (resp. $K_m$, ${\cal K}$), which is
desirable since $K$ (resp. $K_m$, ${\cal K}$)
can range from zero to $O(n^2)$. All of the
above algorithms use optimal $\Theta(n)$ storage. The constants of
proportionality in the big-Oh notation increase as $\epsilon$ decreases.
These results are
based on properties of the sparse nets introduced by Chazelle.