We study versions of cop and robber pursuit-evasion games on the visibility graphs of polygons, and inside polygons with straight and curved sides. Each player has full information about the other player's location, players take turns, and the robber is captured when the cop arrives at the same point as the robber. In visibility graphs we show the cop can always win because visibility graphs are dismantlable, which is interesting as one of the few results relating visibility graphs to other known graph classes. We extend this to show that the cop wins games in which players move along straight line segments inside any polygon and, more generally, inside any simply connected planar region with a reasonable boundary. Essentially, our problem is a type of pursuit-evasion using the link metric rather than the Euclidean metric, and our result provides an interesting class of infinite cop-win graphs.
A draft for here: H.V. Traditional algorithms in computational geometry deal with points and piece wise linear subspaces (lines, segments, polygons, etc.). For real applications we need to handle the environments with curved boundaries. However, the complexity of the curved boundary highly effects the complexity of algorithms. There are some studies those try to solve the problems on curves. In @cite_18 @cite_28 the problem of finding shortest path on special curves like disks and pseudodisks is studied. Some heuristic approaches approximate the curved boundaries by polygons and use the algorithms designed for polygonal domains @cite_1 . The study of algorithms for more general curved inputs initiated by Dobkin and Souvaine in 1990 @cite_14 . They modeled curved boundaries with a finite set of convex splines and call them splinegons''. Each spline, like lines, is in @math complexity, so primitive operations such as finding the intersection of a line with a spline or the common tangents of two splines can be computed in constant time. This model is widely used as a standard model for curved planar environments in different studies.
@cite_28 @cite_18 @cite_14 @cite_1
2040904149 2022670034 2063244634 1964475161
We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others. In this paper, we study the problem of finding Euclidean shortest paths among curved obstacles in the plane. We model curved obstacles as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge, and each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of h pairwise disjoint splinegons with a total of n vertices, we present an algorithm that can compute a shortest path from s to t avoiding the splinegons in O(n+hlogeh+k) time for any e>0, where k is a parameter sensitive to the input splinegons and k=O(h2). If all splinegons are convex, a common tangent of two splinegons is "free" if it does not intersect the interior of any splingegon; our techniques yield an output sensitive algorithm for computing all free common tangents of the h splinegons in O(n+hlogh+k) time and O(n) working space, where k is the number of all free common tangents. The goal of this paper is to show that the concept of the shortest path inside a polygonal region contributes to the design of efficient algorithms for certain geometric optimization problems involving simple polygons: computing optimum separators, maximum area or perimeter-inscribed triangles, a minimum area circumscribed concave quadrilateral, or a maximum area contained triangle. The structure for the algorithms presented is as follows: (a) decompose the initial problem into a low-degree polynomial number of optimization problems; (b) solve each individual subproblem in constant time using standard methods of calculus, basic methods of numerical analysis, or linear programming. These same optimization techniques can be applied to splinegons (curved polygons). First a decomposition technique for curved polygons is developed; this technique is substituted for triangulation in creating equally efficient curved versions of the algorithms for the shortest-path tree, ray-shooting, and two-point shortest path... Introduces a new surface representation for recognizing curved objects. The authors approach begins by representing an object by a discrete mesh of points built from range data or from a geometric model of the object. The mesh is computed from the data by deforming a standard shaped mesh, for example, an ellipsoid, until it fits the surface of the object. The authors define local regularity constraints that the mesh must satisfy. The authors then define a canonical mapping between the mesh describing the object and a standard spherical mesh. A surface curvature index that is pose-invariant is stored at every node of the mesh. The authors use this object representation for recognition by comparing the spherical model of a reference object with the model extracted from a new observed scene. The authors show how the similarity between reference model and observed data can be evaluated and they show how the pose of the reference object in the observed scene can be easily computed using this representation. The authors present results on real range images which show that this approach to modelling and recognizing 3D objects has three main advantages: (1) it is applicable to complex curved surfaces that cannot be handled by conventional techniques; (2) it reduces the recognition problem to the computation of similarity between spherical distributions; in particular, the recognition algorithm does not require any combinatorial search; and (3) even though it is based on a spherical mapping, the approach can handle occlusions and partial views. >