Content deleted Content added
→History: plausible but entirely unsourced; remove |
→Generalizations and extensions: supply requested citation |
||
Line 25:
Topological sweeping is a form of plane sweep with a simple ordering of processing points, which avoids the necessity of completely sorting the points; it allows some sweep line algorithms to be performed more efficiently.
The [[rotating calipers]] technique for designing geometric algorithms may also be interpreted as a form of the plane sweep, in the [[projective dual]] of the input plane: a form of projective duality transforms the slope of a line in one plane into the ''x''-coordinate of a point in the dual plane, so the progression through lines in sorted order by their slope as performed by a rotating calipers algorithm is dual to the progression through points sorted by their ''x''-coordinates in a plane sweep algorithm.<ref>{{
| last1 = Cheung | first1 = Yam Ki
| last2 = Daescu | first2 = Ovidiu
| editor1-last = Goldberg | editor1-first = Andrew V.
| editor2-last = Zhou | editor2-first = Yunhong
| contribution = Line segment facility ___location in weighted subdivisions
| doi = 10.1007/978-3-642-02158-9_10
| pages = 100–113
| publisher = Springer (1)
| series = Lecture Notes in Computer Science
| title = Algorithmic Aspects in Information and Management, 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings
| volume = 5564
| year = 2009}}</ref>
The sweeping approach may be generalised to higher dimensions.<ref>{{cite arXiv |last=Sinclair |first=David |eprint=1602.04707 |title=A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation |class=cs.CG |date=2016-02-11}}</ref>
| |||