The contour problem for rectilinear polygons (Q802313)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3890751
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The contour problem for rectilinear polygons |
scientific article; zbMATH DE number 3890751 |
Statements
The contour problem for rectilinear polygons (English)
0 references
1984
0 references
This paper presents yet another algorithm to solve the contour problem for the union of a set of rectangles or orthogonal polygons. The algorithm is both time- and space-optimal, requiring O(n log n\(+e)\) time and O(n) space, if the input has a total of n vertices and the output has a total of e vertices. The only other algorithm with this performance is the one due to Güting. However his algorithm relies on a complex data structure while the algorithm given here uses a simple variation on the segment tree. Indeed when the input consists solely of rectangles the solution is almost as simple as the original and non-optimal Lipski and Preparata algorithm.
0 references
optimal algorithm
0 references
sweep plane
0 references
scan line
0 references
disjoint-set union
0 references
contour problem
0 references
rectangles
0 references
orthogonal polygons
0 references
segment tree
0 references
0.9116966724395752
0 references
0.9096201062202454
0 references
0.8222838044166565
0 references
0.8085922598838806
0 references
