Results 1 to 10 of about 142,034 (198)
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
On the Complexity of Half-Guarding Monotone Polygons [PDF]
Latin American Symposium on Theoretical Informatics, 2022 15 pages, 19 figures, preliminary version appeared in EuroCG ...
Hannah Miller, Erik Krohn, Alex Pahlow
semanticscholar +6 more sources
Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility [PDF]
International Computing and Combinatorics Conference, 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
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
Covering a Simple Polygon by Monotone Directions
Computational Geometry, 2008 AbstractIn this paper we study the problem of finding a set of k directions for a given simple polygon P, such that for each point p∈P there is at least one direction in which the line through p intersects the polygon only once. For k=1, this is the classical problem of finding directions in which the polygon is monotone, and all such directions can be
Hee-Kap Ahn +4 more
semanticscholar +7 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
Smooth Interpolating Curves with Local Control and Monotone Alternating Curvature. [PDF]
Comput Graph Forum, 2022 We propose a method for the construction of a planar curve based on piecewise clothoids and straight lines that intuitively interpolates a given sequence of control points. Our method has several desirable properties that are not simultaneously fulfilled
Binninger A, Sorkine-Hornung O.
europepmc +2 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