Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Sweep line algorithm
open-in-new
<p>In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, a sweep line algorithm or plane sweep algorithm is an <a href="/facts/Algorithmic_paradigm/KaykS57Y">algorithmic paradigm</a> that uses a conceptual <i>sweep line</i> or <i>sweep surface</i> to solve various problems in <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a>. It is one of the critical techniques in computational geometry. </p><p>The idea behind algorithms of this type is to imagine that a line (often a vertical line) is swept or moved across the plane, stopping at some points. Geometric operations are restricted to geometric objects that either intersect or are in the immediate vicinity of the sweep line whenever it stops, and the complete solution is available once the line has passed over all objects. </p>