# MPI-I-95-1-022

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

### Pellegrini, M.

**MPI-I-95-1-022**. July** **1995, 12 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-95-1-022.pdf | 43445 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-022

**BibTeX**
`@TECHREPORT{``Pellegrini95``,`

` AUTHOR = {Pellegrini, M.},`

` TITLE = {New deterministic algorithms for counting pairs of intersecting segments and off-line triangle range searching},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-95-1-022},`

` MONTH = {July},`

` YEAR = {1995},`

` ISSN = {0946-011X},`

`}`