Search

We describe algorithms to efficiently compute minimum (s, t)-cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph G with n vertices embedded on an orientable surface of genus g, our algorithms can solve either problem in gO(g)nlog log n or 2O(g)nlog n time, whichever is better. When g is a constant, our gO(g)nlog log n time algorithms match the best running times known for computing minimum cuts in planar graphs. Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given Z2-homology class, and we give efficient algorithms for this latter problem as well. If G is embedded on a surface with genus g and b boundary components, these algorithms run in (g + b)O(g+b)nlog log n and 2O(g+b)nlog n time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing that it is likely impossible to improve upon the exponential dependencies on g for this latter problem. [ABSTRACT FROM AUTHOR]

Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number β . We consider the complexity of finding closed directed walks in G that are either contractible (trivial in homotopy) or bounding (trivial in integer homology) in S. Specifically, we describe algorithms to determine whether G contains a simple contractible cycle in O (n + m) time, or a contractible closed walk in O (n + m) time, or a bounding closed walk in O (β (n + m)) time. Our algorithms rely on subtle relationships between strong connectivity in G and in the dual graph G*; our contractible-closed-walk algorithm also relies on a seminal topological result of Hass and Scott. We also prove that detecting simple bounding cycles is NP-hard. We also describe three polynomial-time algorithms to compute shortest contractible closed walks, depending on whether the fundamental group of the surface is free, abelian, or hyperbolic. A key step in our algorithm for hyperbolic surfaces is the construction of a context-free grammar with O (g 2 L 2) non-terminals that generates all contractible closed walks of length at most L, and only contractible closed walks, in a system of quads of genus g ≥ 2 . Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard. Finally, we consider the complexity of detecting negative closed walks with trivial topology, when some edges of the input graph have negative weights. We show that negative bounding walks can be detected in polynomial time, by reduction to maximum flows. We also describe polynomial-time algorithms to find negative contractible walks in graphs on the torus or any surface with boundary; the remaining case of hyperbolic surfaces remains open. The corresponding problems for simple cycles are all NP-hard. [ABSTRACT FROM AUTHOR]

Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with n self-crossings requires $$\Theta (n^{3/2})$$ homotopy moves in the worst case. Our algorithm improves the best previous upper bound $$O(n^2)$$ , which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. Our lower bound also implies that $$\Omega (n^{3/2})$$ facial electrical transformations are required to reduce any plane graph with treewidth $$\Omega (\sqrt{n})$$ to a single vertex, matching known upper bounds for rectangular and cylindrical grid graphs. More generally, we prove that transforming one immersion of k circles with at most n self-crossings into another requires $$\Theta (n^{3/2} + nk + k^2)$$ homotopy moves in the worst case. Finally, we prove that transforming one non-contractible closed curve to another on any orientable surface requires $$\Omega (n^2)$$ homotopy moves in the worst case; this lower bound is tight if the curve is homotopic to a simple closed curve. [ABSTRACT FROM AUTHOR]

We present an $$O(n\log n)$$ -time algorithm that determines whether a given n-gon in the plane is weakly simple. This improves upon an $$O(n^2\log n)$$ -time algorithm by Chang et al. (Proceedings of the 26th ACM-SIAM symposium on discrete algorithm, SIAM, 2015). Weakly simple polygons are required as input for several geometric algorithms. As such, recognizing simple or weakly simple polygons is a fundamental problem. [ABSTRACT FROM AUTHOR]

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the ℓ norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p=1, p even, and p=∞. For p even, we reduce the problem to standard convolution, while for p=∞ and p=1, we reduce the problem to (min,+) convolution and $(\operatorname {median},+)$ convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X+ Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X+ Y matrix. All of our algorithms run in o( n) time, whereas the obvious algorithms for these problems run in Θ( n) time. [ABSTRACT FROM AUTHOR]

Let be a directed graph with vertices and nonnegative weights in its directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. We describe a randomized algorithm to preprocess the graph in O(gn log) time with high probability, so that the shortest-path distance from any vertex on the boundary of f to any other vertex in G can be retrieved in O(log n) time. Our result directly generalizes the O(n log n)-time algorithm of Klein [Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of f. As an application of our algorithm, we describe algorithms to compute a shortest noncontractible or nonseparating cycle in embedded, undirected graphs in O(g²n log n) time with high probability. Our high-probability time bounds hold in the worst case for generic edge weights or with an additional O(log n) factor for arbitrary edge weights. [ABSTRACT FROM AUTHOR]

n essential cycle on a surface is a simple cycle that cannot be continuously deformed to a point or a single boundary. We describe algorithms to compute the shortest essential cycle in an orientable combinatorial surface in O( nlog n) time, or in O( nlog n) time when both the genus and number of boundaries are fixed. Our results correct an error in a paper of Erickson and Har-Peled (Discrete Comput. Geom. 31(1):37-59, ). [ABSTRACT FROM AUTHOR]

A cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. We describe an algorithm to compute a single tight, noncontractible, essentially simple cycle on a given orientable combinatorial surface in O(n log n) time. The only method previously known for this problem was to compute the globally shortest noncontractible or nonseparating cycle in O(min{g³, n} n log n) time, where g is the genus of the surface. As a consequence, we can compute the shortest cycle freely homotopic to a chosen boundary cycle in O(n log n) time, a tight octagonal decomposition in O(gn log n) time, and a shortest contractible cycle enclosing a nonempty set of faces in O(n log² n) time. [ABSTRACT FROM AUTHOR]

The Centerpoint Theorem states that, for any set S of n points in ℝd, there exists a point p in ℝd such that every closed halfspace containing p contains at least ⌈n/(d + 1)⌉ points of S. We consider generalizations of the Centerpoint Theorem in which halfspaces are replaced with wedges (cones) of angle α. In ℝ2, we give bounds that are tight for all values of α and give an O(n) time algorithm to find a point satisfying these bounds. We also give partial results for ℝ3 and, more generally, ℝd. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent disc-shaped robots. Given two stationary robots in contact with P, we characterize the set of positions of a third robot, the so-called capture region, that prevent P from escaping to infinity via continuous rigid motion. We show that the computation of the capture region reduces to a visibility problem. We present two algorithms for solving this problem, and for computing the capture region when P is a polygon and the robots are points (zero-radius discs). The first algorithm is exact and has polynomial time complexity. The second one uses simple hidden surface removal techniques from computer graphics to output an arbitrarily accurate approximation of the capture region; it has been implemented, and examples are presented. [ABSTRACT FROM AUTHOR]

We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords. [ABSTRACT FROM AUTHOR]

Abstract: We introduce a new realistic input model for straight-line geometric graphs and nonconvex polyhedra. A geometric graph G is local if (1) the longest edge at every vertex v is only a constant factor longer than the distance from v to its Euclidean nearest neighbor among the other vertices of G and (2) the longest and shortest edges of G differ in length by at most a polynomial factor. A polyhedron is local if all its faces are simplices and its edges form a local geometric graph. We show that any boolean combination of two local polyhedra in , each with n vertices, can be computed in time using a standard hierarchy of axis-aligned bounding boxes. Using results of de Berg, we also show that any local polyhedron in has a binary space partition tree of size and depth ; these bounds are tight in the worst case when . Finally, we describe efficient algorithms for computing Minkowski sums of local polyhedra in two and three dimensions. [Copyright &y& Elsevier]

This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines. [ABSTRACT FROM AUTHOR]

Abstract: Let be an orientable combinatorial surface. A cycle on is splitting if it has no self-intersections and it partitions into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus g and the number of boundary components b of the surface. Specifically, we describe an algorithm to compute the shortest splitting cycle in time, where n is the complexity of the combinatorial surface. [Copyright &y& Elsevier]