日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

報告書

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

MPS-Authors
/persons/resource/persons72898

Pellegrini,  M.
Department of Human Evolution, Max Planck Institute for Evolutionary Anthropology, Max Planck Society;

External Resource
There are no locators available
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)

MPI-I-95-1-022.pdf
(全文テキスト(全般)), 43MB

付随資料 (公開)
There is no public supplementary material available
引用

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.


引用: https://hdl.handle.net/11858/00-001M-0000-0014-A1E9-4
要旨
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.