66:
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,
197:
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.
213:-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
20:
335:
173:
Since then, this approach has been used to design efficient algorithms for a number of problems in computational geometry, such as the construction of the
87:
design, in which a geometric description of an IC was processed in parallel strips because the entire description could not fit into memory.
328:
321:
107:
in the plane in 1976. In particular, they described how a combination of the scanline approach with efficient data structures (
108:
296:
Sinclair, David (2016-02-11). "A 3D Sweep Hull
Algorithm for computing Convex Hulls and Delaunay Triangulation".
186:
582:
135:
513:
483:
468:
205:
technique for designing geometric algorithms may also be interpreted as a form of the plane sweep, in the
277:
587:
538:
412:
402:
382:
209:
of the input plane: a form of projective duality transforms the slope of a line in one plane into the
417:
104:
84:
556:
518:
362:
182:
178:
96:
36:
24:
422:
392:
508:
453:
48:
8:
543:
528:
473:
561:
463:
458:
372:
297:
255:
237:
100:
76:
523:
367:
202:
80:
503:
488:
247:
259:
67:
and the complete solution is available once the line has passed over all objects.
478:
313:
206:
174:
116:
60:
28:
344:
273:
121:
576:
493:
448:
443:
407:
377:
397:
251:
16:
Class of algorithms which use a moving line to solve geometrical problems
387:
241:
19:
348:
111:) makes it possible to detect whether there are intersections among
302:
63:. It is one of the critical techniques in computational geometry.
498:
243:
Proc. 17th IEEE Symp. Foundations of
Computer Science (FOCS '76)
220:
The sweeping approach may be generalised to higher dimensions.
83:, followed by exploiting this approach in early algorithms of
427:
95:
Application of this approach led to a breakthrough in the
240:; Hoey, Dan (1976), "Geometric intersection problems",
279:
Line
Segment Intersection Using a Sweep Line Algorithm
343:
192:
574:
329:
146:segments in the plane in time complexity of
336:
322:
236:
138:uses a sweep line technique to report all
27:, a sweep line technique for constructing
301:
217:-coordinates in a plane sweep algorithm.
295:
272:
18:
575:
317:
13:
109:self-balancing binary search trees
103:and Hoey presented algorithms for
14:
599:
90:
75:This approach may be traced to
289:
266:
230:
193:Generalizations and extensions
187:boolean operations on polygons
1:
223:
99:of geometric algorithms when
59:to solve various problems in
7:
10:
604:
70:
552:
436:
355:
136:Bentley–Ottmann algorithm
115:segments in the plane in
105:line segment intersection
85:integrated circuit layout
162:and space complexity of
142:intersections among any
97:computational complexity
557:List of data structures
51:that uses a conceptual
183:Delaunay triangulation
134:. The closely related
37:computational geometry
32:
45:plane sweep algorithm
22:
583:Geometric algorithms
454:Breadth-first search
252:10.1109/SFCS.1976.16
246:, pp. 208–215,
49:algorithmic paradigm
41:sweep line algorithm
544:Topological sorting
474:Dynamic programming
179:Fortune's algorithm
77:scanline algorithms
25:Fortune's algorithm
562:List of algorithms
469:Divide and conquer
464:Depth-first search
459:Brute-force search
373:Binary search tree
238:Shamos, Michael I.
33:
588:1976 in computing
570:
569:
368:Associative array
203:rotating calipers
81:computer graphics
595:
539:String-searching
338:
331:
324:
315:
314:
308:
307:
305:
293:
287:
285:
284:
270:
264:
262:
234:
169:
161:
145:
141:
133:
114:
79:of rendering in
29:Voronoi diagrams
603:
602:
598:
597:
596:
594:
593:
592:
573:
572:
571:
566:
548:
479:Graph traversal
432:
356:Data structures
351:
345:Data structures
342:
312:
311:
294:
290:
282:
274:Souvaine, Diane
271:
267:
235:
231:
226:
207:projective dual
195:
175:Voronoi diagram
163:
147:
143:
139:
120:
117:time complexity
112:
93:
73:
61:Euclidean space
17:
12:
11:
5:
601:
591:
590:
585:
568:
567:
565:
564:
559:
553:
550:
549:
547:
546:
541:
536:
531:
526:
521:
516:
511:
506:
501:
496:
491:
486:
481:
476:
471:
466:
461:
456:
451:
446:
440:
438:
434:
433:
431:
430:
425:
420:
415:
410:
405:
400:
395:
390:
385:
380:
375:
370:
365:
359:
357:
353:
352:
341:
340:
333:
326:
318:
310:
309:
288:
265:
228:
227:
225:
222:
194:
191:
92:
89:
72:
69:
15:
9:
6:
4:
3:
2:
600:
589:
586:
584:
581:
580:
578:
563:
560:
558:
555:
554:
551:
545:
542:
540:
537:
535:
532:
530:
527:
525:
522:
520:
517:
515:
512:
510:
507:
505:
502:
500:
497:
495:
494:Hash function
492:
490:
487:
485:
482:
480:
477:
475:
472:
470:
467:
465:
462:
460:
457:
455:
452:
450:
449:Binary search
447:
445:
442:
441:
439:
435:
429:
426:
424:
421:
419:
416:
414:
411:
409:
406:
404:
401:
399:
396:
394:
391:
389:
386:
384:
381:
379:
376:
374:
371:
369:
366:
364:
361:
360:
358:
354:
350:
346:
339:
334:
332:
327:
325:
320:
319:
316:
304:
299:
292:
281:
280:
275:
269:
261:
257:
253:
249:
245:
244:
239:
233:
229:
221:
218:
216:
212:
208:
204:
199:
190:
188:
184:
180:
176:
171:
167:
159:
155:
151:
137:
131:
127:
123:
118:
110:
106:
102:
98:
88:
86:
82:
78:
68:
64:
62:
58:
57:sweep surface
54:
50:
46:
42:
38:
30:
26:
23:Animation of
21:
533:
519:Root-finding
444:Backtracking
408:Segment tree
378:Fenwick tree
291:
278:
268:
242:
232:
219:
214:
210:
200:
196:
172:
165:
157:
153:
149:
129:
125:
94:
91:Applications
74:
65:
56:
52:
44:
40:
34:
398:Linked list
577:Categories
534:Sweep line
509:Randomized
437:Algorithms
388:Hash table
349:algorithms
303:1602.04707
224:References
181:) and the
53:sweep line
529:Streaming
514:Recursion
276:(2008),
524:Sorting
499:Minimax
71:History
504:Online
489:Greedy
418:String
260:124804
258:
156:) log
101:Shamos
47:is an
413:Stack
403:Queue
383:Graph
363:Array
298:arXiv
283:(PDF)
256:S2CID
484:Fold
428:Trie
423:Tree
393:Heap
347:and
201:The
128:log
39:, a
248:doi
185:or
148:O((
119:of
55:or
43:or
35:In
579::
254:,
189:.
170:.
164:O(
152:+
337:e
330:t
323:v
306:.
300::
286:.
263:.
250::
215:x
211:x
177:(
168:)
166:N
160:)
158:N
154:K
150:N
144:N
140:K
132:)
130:N
126:N
124:(
122:O
113:N
31:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
