๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Computing a single cell in the overlay of two simple polygons

โœ Scribed by Mark de Berg; Olivier Devillers; Katrin Dobrindt; Otfried Schwarzkopf

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
485 KB
Volume
63
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

This note combines the lazy randomized incremental construction scheme with the technique of "connectivity acceleration" to obtain an 0( n( log* n)*) time randomized algorithm to compute a single face in the overlay of two simple polygons in the plane. @

๐Ÿ“œ SIMILAR VOLUMES

Computing the link center of a simple po
Computing the link center of a simple polygon
โœ W. Lenhart; R. Pollack; J. Sack; R. Seidel; M. Sharir; S. Suri; G. Toussaint; S. ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Springer ๐ŸŒ English โš– 778 KB
Optimally Computing the Shortest Weakly
Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon
โœ Danny Z. Chen ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 209 KB

Given an n-vertex simple polygon P, the problem of computing the shortest weakly visible subedge of P is that of finding a shortest line segment s on the ลฝ . boundary of P such that P is weakly visible from s if s exists . In this paper, we present new geometric observations that are useful for solv