Sweep line algorithm: Difference between revisions

Revision as of 05:42, 29 March 2017

Revision as of 05:42, 29 March 2017

Line 25:

==Generalizations and extensions==

Topological sweeping is a form of the plane sweep with a relaxed ordering of processing points, thatwhich 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 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.