Approximation Algorithms for the Two-Watchman Route in a Simple Polygon [PDF]
Algorithmica, 2023 The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized.
Bengt J. Nilsson, Eli Packer
openalex +3 more sources
Flip Distance Between Triangulations of a Simple Polygon is NP-Complete [PDF]
Discrete & Computational Geometry, 2017 Let T be a triangulation of a simple polygon. A flip in T is the operation of removing one diagonal of T and adding a different one such that the resulting graph is again a triangulation.
A Pilz +19 more
core +3 more sources
Shortest path in a polygon using sublinear space [PDF]
Journal of Computational Geometry, 2015 We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time.
Sariel Har-Peled
doaj +5 more sources
Weak Visibility Queries of Line Segments in Simple Polygons [PDF]
, 2012 Given a simple polygon P in the plane, we present new algorithms and data structures for computing the weak visibility polygon from any query line segment in P. We build a data structure in O(n) time and O(n) space that can compute the visibility polygon
Chen, Danny Z., Wang, Haitao
core +3 more sources
Geodesic Fréchet distance inside a simple polygon [PDF]
TALG, 2010 We present an alternative to parametric search that applies to both the nongeodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance and practical ...
Atlas F. Cook, Carola Wenk
openalex +3 more sources
An Upper Bound for Min-Max Angle of Polygons [PDF]
Mathematics Interdisciplinary Research, 2023 Let $S$ be a set of $n$ points in the plane, $\nabla(S)$ the set of all simple polygons crossing $S$, $\gamma_P$ the maximum angle of polygon $P \in \nabla(S)$ and $\theta =min_{P\in\nabla(S)} \gamma_P$.
Saeed Asaeedi +2 more
doaj +1 more source
Innovation Characteristics in Configuring Farmers’ Digital Literacy on E-Reporting Polygon in Wukirsari Indonesia [PDF]
BIO Web of Conferences, 2023 The e-reporting polygon is an effort of the Ministry of Agriculture to maximize agricultural cultivation activities, especially on the availability of subsidized fertilizers.
Shania Alya Hisna +2 more
doaj +1 more source
Computing All Immobilizing Grasps of a Simple Polygon with Few Contacts [PDF]
Algorithmica, 2005 Jae-Sook Cheong +2 more
openalex +2 more sources
A simple polygon-polygon basis method to compare categorical raster maps [PDF]
International Journal for Simulation and Multidisciplinary Design Optimization, 2009 In this paper we present a method for comparing categorical raster maps based on comparing categories at the polygon level. In contrast with the most commonly used pixel-level methods of comparison, the proposed method reduces both possible map ...
Ordóñez Celestino +3 more
doaj +1 more source
A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 Discrete ...
Sergio Cabello, Maria Saumell
doaj +1 more source