Results 11 to 20 of about 148,856 (241)
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
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 +5 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
Lower Bound for Sculpture Garden Problem: Localization of IoT Devices
Applied Sciences, 2023 The purpose of the current study is to investigate a special case of art gallery problem, namely a sculpture garden problem. In this problem, for a given polygon P, the ultimate goal is to place the minimum number of guards (landmarks) to define the ...
Marzieh Eskandari +2 more
doaj +2 more sources
Line-of-Sight Pursuit in Monotone and Scallop Polygons [PDF]
International Journal of Computational Geometry & Applications, 2019 We study a turn-based game in a simply connected polygonal environment [Formula: see text] between a pursuer [Formula: see text] and an adversarial evader [Formula: see text]. Both players can move in a straight line to any point within unit distance during their turn.
Lindsay Berry +6 more
openalex +5 more sources
Approximate Guarding of Monotone and Rectilinear Polygons [PDF]
, 2005 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.
Bengt J. Nilsson
openalex +5 more sources
Separation of two monotone polygons in linear time [PDF]
Robotica, 1984 SUMMARYLet P= (p1, p2, …, pn) and Q= (q1, q2, …, qm) be two simple polygons monotonic in directions θs and φ respectively. It is shown that P and Q are separable with a single translation in at least one of the directions: ,. Furthermore, a direction for carrying out such a translation can be determined in O(m + n) time.
Godfried T. Toussaint +1 more
openalex +3 more sources
Linear-time algorithms for weakly-monotone polygons
Computational Geometry, 1993 Triangulating a simple polygon is possible in linear time. But the corresponding algorithm is too complex to be considered practical. Simple optimal algorithms for special classes of polygons are interesting. The author studies a new class of so-called weakly-monotone polygons which contains the monotone class.
Paul J. Heffernan
openalex +3 more sources
The VC-dimension of visibility on the boundary of monotone polygons
Computational Geometry, 2018 Abstract We show that the VC-dimension of visibility on the boundary of a monotone polygon is exactly 6. Our lower bound construction matches the best known lower bound for simple polygons.
Matt Gibson, Erik Krohn, Qing Wang
openalex +3 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