Results 1 to 10 of about 148,856 (241)
Lion and man with visibility in monotone polygons [PDF]
The International Journal of Robotics Research, 2013 In the original version of the lion and man game, a lion tries to capture a man who is trying to escape in a circular arena. The players have equal speeds. They can observe each other at all times. We study a new variant of the game in which the lion has only line-of-sight visibility.
Narges Noori, Volkan Isler
semanticscholar +6 more sources
Approximate Guarding of Monotone and Rectilinear Polygons [PDF]
Algorithmica, 2012 We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding 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
semanticscholar +8 more sources
Minkowski Sums of Monotone and General Simple Polygons [PDF]
Discrete & Computational Geometry, 2005 Let P be a simple polygon with m edges, which is the disjoint union of k simple polygons, all monotone in a common direction u, and let Q be another simple polygon with n edges, which is the disjoint union of l simple polygons, all monotone in a common direction v. We show that the combinatorial complexity of the Minkowski sum P ź Q is O(klmnź(min{m,n})
Eduard Oks, Micha Sharir
semanticscholar +5 more sources
Convexifying Monotone Polygons [PDF]
International Symposium on Algorithms and Computation, 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
semanticscholar +6 more sources
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 +6 more sources
Rotationally monotone polygons [PDF]
Computational Geometry, 2007 AbstractWe introduce a generalization of monotonicity. An n-vertex polygon P is rotationally monotone with respect to a point r if there exists a partitioning of the boundary of P into exactly two polygonal chains, such that one chain can be rotated clockwise around r and the other chain can be rotated counterclockwise around r with neither chain ...
Prosenjit Bose +3 more
openalex +3 more sources
Planar lower envelope of monotone polygonal chains [PDF]
Information Processing Letters, 2015 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 +4 more sources
Modem illumination of monotone polygons [PDF]
Computational Geometry, 2017 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
openalex +3 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
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 +5 more sources