Content deleted Content added
Balaban 1995 reference from Suresh V. |
Chen and Chan 2003 |
||
Line 36:
If the crossings found by the algorithm do not need to be stored once they have been found, the space used by the algorithm at any point in time is O(''n''): each of the ''n'' input line segments corresponds to at most one node of the binary search tree ''T'', and as stated above the event queue contains at most 3''n'' elements. This space bound is due to {{harvtxt|Brown|1981}}; the original version of the algorithm was slightly different (it did not remove crossing events from ''Q'' when some other event causes the two crossing segments to become non-adjacent) causing it to use more space.<ref>The nonlinear space complexity of the original version of the algorithm was analyzed by {{harvtxt|Pach|Sharir|1991}}.</ref>
{{harvtxt|Chen|Chan|2003}} described a highly space-efficient version of the Bentley–Ottman algorithm that encodes most of its information in the ordering of the segments in an array representing the input, requiring only O(log<sup>2</sup>''n'') additional memory cells. However, in order to access the encoded information, the algorithm is slowed by a logarithmic factor.
==Special position and numerical precision issues==
Line 62 ⟶ 64:
*{{citation|last=Brown|first=K. Q.|title=Comments on “Algorithms for Reporting and Counting Geometric Intersections”|journal=IEEE transactions on Computers|year=1981|volume=C-30|issue=2|page=147}}.
*{{citation|last1=Chazelle|first1=Bernard|author1-link=Bernard Chazelle|last2=Edelsbrunner|first2=Herbert|author2-link=Herbert Edelsbrunner|title=An optimal algorithm for intersecting line segments in the plane|journal=[[Journal of the ACM]]|volume=39|issue=1|pages=1–54|year=1992|doi=10.1145/147508.147511}}.
*{{citation|last1=Chen|first1=E. Y.|last2=Chan|first2=T. M.|author2-link=Timothy M. Chan|contribution=A space-efficient algorithm for segment intersection|title=Proc. 15th Canadian Conference on Computational Geometry|year=2003|url=http://www.cccg.ca/proceedings/2003/31.pdf}}.
*{{citation|last=Clarkson|first=K. L.|authorlink=Kenneth L. Clarkson|contribution=Applications of random sampling in computational geometry, II|title=Proc. 4th ACM Symp. Computational Geometry|pages=1–11|year=1988|doi=10.1145/73393.73394}}.
*{{citation|last1=Clarkson|first1=K. L.|author1-link=Kenneth L. Clarkson|last2=Cole|first2=R.|last3=Tarjan|first3=R. E.|author3-link=Robert Tarjan|title=Randomized parallel algorithms for trapezoidal diagrams|journal=International Journal of Computational Geometry and Applications|volume=2|issue=2|year=1992|pages=117–133}}. Corrigendum, '''2''' (3): 341–343.
| |||