Results 1 to 10 of about 5,737 (222)
A simple algorithm for computing positively weighted straight skeletons of monotone polygons.
Inf Process Lett, 2015 We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in [Formula: see text] time and [Formula: see text] space, where n denotes the number of vertices of the polygon.
Biedl T +4 more
europepmc +5 more sources
Approximate Guarding of Monotone and Rectilinear Polygons [PDF]
Algorithmica, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bengt J. Nilsson
openalex +6 more sources
Modem Illumination of Monotone Polygons
Computational Geometry, 2015 We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$-modems and study the minimum number of $k$-modems sufficient and sometimes necessary to illuminate monotone and monotone
Oswin Aichholzer +5 more
+7 more sources
Altitude terrain guarding and guarding uni-monotone polygons [PDF]
Computational Geometry, 2019 We present an optimal, linear-time algorithm for the following version of terrain guarding: given a 1.5D terrain and a horizontal line, place the minimum number of guards on the line to see all of the terrain. We prove that the cardinality of the minimum guard set coincides with the cardinality of a maximum number of ``witnesses'', i.e., terrain points,
Ovidiu Daescu +4 more
openalex +6 more sources
Convexifying Monotone Polygons [PDF]
, 1999 This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a convex polygon; a polygon is monotone if any vertical line intersects the interior at a (possibly empty) interval.
Thérèse Biedl +4 more
openalex +4 more sources
On the Complexity of Half-Guarding Monotone Polygons [PDF]
, 2022 15 pages, 19 figures, preliminary version appeared in EuroCG ...
Hannah Miller, Erik Krohn, Alex Pahlow
+5 more sources
Approximate Guarding of Monotone and Rectilinear Polygons [PDF]
, 2012 We show a constant factor approximation algorithm for interior guarding of monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon.
Erik Krohn, Bengt J. Nilsson
openalex +4 more sources
Planar lower envelope of monotone polygonal chains [PDF]
Information Processing Letters, 2014 A simple linear search algorithm running in $O(n+mk)$ time is proposed for constructing the lower envelope of $k$ vertices from $m$ monotone polygonal chains in 2D with $n$ vertices in total. This can be applied to output-sensitive construction of lower envelopes for arbitrary line segments in optimal $O(n\log k)$ time, where $k$ is the output size ...
Daniel L. Lu
openalex +5 more sources
Any Monotone Function Is Realized by Interlocked Polygons [PDF]
Algorithms, 2012 Suppose there is a collection of n simple polygons in the plane, none of which overlap each other. The polygons are interlocked if no subset can be separated arbitrarily far from the rest. It is natural to ask the characterization of the subsets that makes the set of interlocked polygons free (not interlocked).
Erik D. Demaine +2 more
+9 more sources
Shortest Watchman Tours in Simple Polygons Under Rotated Monotone Visibility [PDF]
, 2020 We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $θ$, while $θ$ varies in $[0,180^{\circ})$, obtaining the directions for the tour to be the shortest one over all tours, where $n$ is the number of vertices, $r$ is the number of ...
Bengt J. Nilsson +4 more
openalex +5 more sources