We introduce a new class of problems concerned with the computation of maximum flows through two-dimensional polyhedral domains. Given a polyhedral space (e.g., a simple polygon with holes), we want to find the maximum “flow” from a source edge to a sink edge. Flow is defined to be a divergence-free vector field on the interior of the domain, and capacity constraints are specified by giving the maximum magnitude of the flow vector at any point. The problem is the natural extension to the continuous domain of the discrete problem of finding maximum flows through a capacitated network. For this problem, Strang proved that max flow equals min cut; we address the problem of constructing min cuts and max flows. We give polynomial-time algorithms for maximum flow from a source edge to a sink edge through a simple polygon with uniform capacity constraint (with or without holes), maximum flow through a simple polygon from many sources to many sinks, and maximum flow through weighted polygonal regions. Central to our methodology is the intimate connection between the max-flow problem and its dual, the min-cut problem. We show how the continuous Dijkstra paradigm of solving shortest paths problems corresponds to a continuous version of the uppermost path algorithm for computation of maximum flow in a planar network.
Recent advances in the field of computational geometry have provided efficient algorithms for a variety of shortest path problems. Many problems in the field of terrain navigation can be cast as optimal path problems in a precise geometric model. With such a model one can develop and analyze algorithms for the solution of the original problem and can gain insights into how to design more efficient heuristics to deal with more complex problems. We examine the path planning problem in which we are given a “map” of a region of terrain and we are expected to find optimal paths from one point to another. This, for example, is a task which must be done repeatedly for the guidance of an autonomous vehicle. We examine how to formulate some path planning problems precisely, and we report algorithms to solve certain special cases.
Set Cover is a well-studied problem with application in many fields. A well-known variant of this problem is the Minimum Membership Set Cover problem: Given a set of points and a set of objects, the objective is to cover all points while minimizing the maximum number of objects that contain any one point. A dual of this problem is the Minimum Membership Hitting Set problem: Given a set of points and a set of objects, the objective is to stab all of the objects while minimizing the maximum number of points that an object contains. We study both of these variants in a geometric setting with various types of geometric objects in the plane, including axis-parallel line segments, axis-parallel strips, rectangles that are anchored on a horizontal line from one side, rectangles that are stabbed by a horizontal line, and rectangles that are anchored on one of two horizontal lines (i.e., each rectangle shares its top or its bottom edge (or both) with one of the input horizontal lines). For each of these problems we either prove NP-hardness or we give a polynomial-time algorithm. In particular, we show that it is NP-complete to decide whether there exists a solution with depth exactly 1 for either the Minimum Membership Set Cover or the Minimum Membership Hitting Set problem. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.
We consider the following problem: given a set S of n points in the plane, we would like to compute for each point pϵS, how many triangles with corners at points in set S contain p. We give an O(n2) algorithm to solve the problem.
DOI : 10.1016/0020-0190(90)90217-l Anahtar Kelimeler :
Range query, computational geometry, combinatorics
ISSN: 0020-0190 Sayı: 6 Cilt: 33 Sayfa: 319-321
We present a linear-time algorithm for computing a triangulation of n points in 2D whose positions are constrained to n disjoint disks of uniform size, after O(nlogn) preprocessing applied to these disks. Our algorithm can be extended to any collection of convex sets of bounded areas and aspect ratios, assuming no point lies in more than some constant number of sets (bounded depth of overlap), and each set contains only a constant number of query points.
Given a family of disjoint polygons P1, P2,…, Pk in the plane, and an integer parameter m, it is NP-complete to decide if the Pi's can be pairwise separated by a polygonal family with at most m edges, that is, if there exist polygons R1, R2,…, Rk with pairwise-disjoint boundaries such that Pi⊆Ri and Σ|Ri|≤m. In three dimensions, the problem is NP-complete even for two nested convex polyhedra. Many other extensions and generalizations of the polyhedral separation problem, either to families of polyhedra or to higher dimensions, are also intractable. In this paper, we present efficient approximation algorithms for constructing separating families of near-optimal size. Our main results are as follows. In two dimensions, we give an O(n log n) time algorithm for constructing a separating family whose size is within a constant factor of an optimal separating family; n is the number of edges in the input family of polygons. In three dimensions, we show how to separate a convex polyhedrom from a nonconvex polyhedron with a polyhedral surface whose facet-complexity is O(log n) times the optimal, where n=|P|+|Q| is the complexity of the input polyhedra. Our algorithm runs in O(n4) time, but improves to O(n3) time if the two polyhedra are nested and convex. Our algorithm for separating a convex polyhedron from a nonconvex polyhedron extends to higher dimensions. In d dimensions, for d≥4, the facet-complexity of the approximation polyhedron is O(d log n) times the optimal, and the algorithm runs in O(nd+1) time. Finally, we also obtain results on separating sets of points, a family of convex polyhedra, and separation by non-polyhedral surfaces, such as spherical patches.
We present an art gallery theorem for simple polygons having n vertices in terms of the number, r, of reflex vertices and the number, c, of convex vertices ( n=r+c). Tight combinatorial bounds have previously been shown when 0⩽r⩽⌊c2⌋ and when r⩾5c−12. We give a lower bound construction that matches the ⌊n3⌋ sufficiency condition from the traditional art gallery theorem when ⌊c2⌋
DOI : 10.1016/j.ipl.2012.07.005 Anahtar Kelimeler :
Computational geometry, Art gallery theorem, Visibility coverage, Guard number
ISSN: 0020-0190 Sayı: 20 Cilt: 112 Sayfa: 778-782
In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. As a generalization of the classical Euclidean TSP, TSPN is also NP-hard. In this paper, we present new approximation results for the TSPN, including (1) a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and (2) a PTAS for the important special case of disjoint unit disk neighborhoods (or nearly disjoint, nearly-unit disks). Our methods also yield improved approximation ratios for various special classes of neighborhoods, which have previously been studied. Further, we give a linear-time O(1)-approximation algorithm for the case of neighborhoods that are (infinite) straight lines.
We give the first polynomial-time algorithm for the problem of finding a minimum-perimeter k-gon that encloses a given n-gon. Our algorithm is based on a simple structural result, that an optimal k-gon has at least one “flush” edge with the n-gon. This allows one to reduce the problem to computing a shortest k-link path in a simple polygon. As a by-product we observe that the minimum-perimeter “envelope”—a convex polygon with a specified sequence of interior angles—can also be found in polynomial time. Finally, we introduce the problem of finding optimal convex polygons restricted to lie in the region between two nested convex polygons. We give polynomial-time algorithms for the problems of finding the minimum restricted envelopes.
This paper presents a method for finding large empty convex bodies within a 3D scene of polygonal models. The convex bodies we pack are discrete orientation polytopes (k-dops) with a small number of facets. The algorithm searches for a large empty k-dop within the scene, using a combination of random sampling and physical simulation, allowing the body to grow and interact (via rotation, translation, and scaling) with the environment when collisions are detected. We pack multiple empty k-dops in a 3D scene using a greedy incremental approach, attempting to maximize the volume of each new body found. We demonstrate the practicality of our method experimentally, showing that it is fast and that it does an effective job of packing on a variety of models.
DOI : 10.1109/iccsa.2008.25 Anahtar Kelimeler :
Layout, Shape, Hardware, Application software, Computer science, Face detection, Sampling methods, Data acquisition, Rendering (computer graphics), Engineering profession, computational geometry, greedy algorithms, optimisation, search problems, solid modelling, large empty convex bodies, 3D scenes, polygonal models, discrete orientation polytopes, search algorithm, random sampling, physical simulation, multiple empty k-dop packing, greedy incremental approach, local optimization, Computational Geometry, k-dop, Ray Tracing, convex body
A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case ( C=2). We study exact and approximation algorithms for minimum-link C-oriented paths and paths with unrestricted orientations, both in C-oriented and in general domains. Our two main algorithms are as follows: A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains. An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm. We also obtain several related results: • 3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain). • An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones. • An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain. • A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path. • A notion of “robust” paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1.
DOI : 10.1016/j.comgeo.2013.12.005 Anahtar Kelimeler :
Path planning, Link distance, Approximations, 3SUM-hardness
ISSN: 0925-7721 Sayı: 6 Cilt: 47 Sayfa: 651-667
Given a set L of non-parallel lines in the plane, a watchman route (tour) for L is a closed curve contained in the union of the lines in L such that every line is visited (intersected) by the route; we similarly define a watchman route (tour) for a connected set S of line segments. The watchman route problem for a given set of lines or line segments is to find a shortest watchman route for the input set, and these problems are natural special cases of the watchman route problem in a polygon with holes (a polygonal domain). In this paper, we show that the problem of computing a shortest watchman route for a set of n non-parallel lines in the plane is polynomially tractable, while it becomes NP-hard in 3D. We give an alternative NP-hardness proof of this problem for line segments in the plane and obtain a polynomial-time approximation algorithm with ratio O(log3n). Additionally, we consider some special cases of the watchman route problem on line segments, for which we provide exact algorithms or improved approximations.
We prove that a triangular grid without local cuts is (almost) always Hamiltonian. This suggests an efficient scheme for rendering triangulated manifolds by graphics hardware. We also show that the Hamiltonian Cycle problem is NP-Complete for planar subcubic graphs of arbitrarily high girth. As a by-product we prove that there exist tri-Hamiltonian planar subcubic graphs of arbitrarily high girth.
We study a class of geometric stabbing/covering problems for sets of line segments, rays and lines in the plane. While we demonstrate that the problems on sets of horizontal/vertical line segments are NP-complete, we show that versions involving (parallel) rays or lines are polynomially solvable.
We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem. Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion. Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1.
We give a simple O(nlogn) algorithm to compute the convex hull of the (possibly Θ(n2)) intersection points in an arrangement of n line segments in the plane. We also show an arrangement of dn hyperplanes in d-dimensions whose arrangement has Θ(nd−1) intersection points on the convex hull.
DOI : 10.1016/j.ipl.2008.03.024 Anahtar Kelimeler :
Computational geometry, Analysis of algorithms
ISSN: 0020-0190 Sayı: 5 Cilt: 107 Sayfa: 194-197
Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set P of n points in the plane, find a spanning tree of P of minimum “area”, where the area of a spanning tree T is the area of the union of the n−1 disks whose diameters are the edges in T. We prove that the Euclidean minimum spanning tree of P is a constant-factor approximation for mast. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (mara) problem, for the Minimum-Area Connected Disk Graph (macdg) problem, and for the Minimum-Area Tour (mat) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.
DOI : 10.1016/j.comgeo.2006.03.001 Anahtar Kelimeler :
Geometric optimization, Approximation algorithms, Minimum spanning tree, Range assignment, Disk graphs, Traveling salesperson problem
ISSN: 0925-7721 Sayı: 3 Cilt: 35 Sayfa: 218-225
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting wire structure (a carpenter's ruler) can be straightened, a problem that was open for several years and has only recently been solved in the affirmative. If we impose some of the constraints that are imposed by the manufacturing process, we obtain quite different results. In particular, we study the variant of the carpenter's ruler problem in which there is a restriction that only one joint can be modified at a time. For a linkage that does not self-intersect or self-touch, the recent results of Connelly et al. and Streinu imply that it can always be straightened, modifying one joint at a time. However, we show that for a linkage with even a single vertex degeneracy, it becomes NP-hard to decide if it can be straightened while altering only one joint at a time. If we add the restriction that each joint can be altered at most once, we show that the problem is NP-complete even without vertex degeneracies. In the special case, arising in wire forming manufacturing, that each joint can be altered at most once, and must be done sequentially from one or both ends of the linkage, we give an efficient algorithm to determine if a linkage can be straightened.
The problem of generating “random” geometric objects is motivated by the need to generate test instances for geometric algorithms. We examine the specific problem of generating a random x-monotone polygon on a given set of n vertices. Here, “random” is taken to mean that we select uniformly at random a polygon, from among all those x-monotone polygons having the given n vertices. We give an algorithm that generates a random monotone polygon in O(n) time and space after O(K) preprocessing time, where n < K < n2 is the number of edges of the visibility graph of the x-monotone chain of the given vertex set. We also give an O(n3) time algorithm for generating a random convex polygon whose vertices are a subset of a given set of n points. Finally, we discuss some further extensions, as well as the challenging open problem of generating random simple polygons.
Given a set S of n points in the plane, we compute in time O(n3) the total number of convex polygons whose vertices are a subset of S. We give an O(m · n3) algorithm for computing the number of convex k-gons with vertices in S, for all values k = 3,…, m; previously known bounds were exponential ( O(n⌜k2⌝). We also compute the number of empty convex polygons (resp.,k-gons, k ⩽ m) with vertices in S in time O(n3) (resp., O(m · n3)).
We study the problem of finding shortest tours/paths for “lawn mowing” and “milling” problems: Given a region in the plane, and given the shape of a “cutter” (typically, a circle or a square), find a shortest tour/path for the cutter such that every point within the region is covered by the cutter at some position along the tour/path. In the milling version of the problem, the cutter is constrained to stay within the region. The milling problem arises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray painting, and optimal search planning. Both problems are NP-hard in general. We give efficient constant-factor approximation algorithms for both problems. In particular, we give a (3+ε)-approximation algorithm for the lawn mowing problem and a 2.5-approximation algorithm for the milling problem. Furthermore, we give a simple 65-approximation algorithm for the TSP problem in simple grid graphs, which leads to an 115-approximation algorithm for milling simple rectilinear polygons.
We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of O(logn).
We show a remarkable fact about folding paper: from a single rectangular sheet of paper, one can fold it into a flat origami that takes the (scaled) shape of any connected polygonal region, even if it has holes. This resolves a long-standing open problem in origami design. Our proof is constructive, utilizing tools of computational geometry, resulting in efficient algorithms for achieving the target silhouette. We show further that if the paper has a different color on each side, we can form any connected polygonal pattern of two colors. Our results apply also to polyhedral surfaces, showing that any polyhedron can be “wrapped” by folding a strip of paper around it. We give three methods for solving these problems: the first uses a thin strip whose area is arbitrarily close to optimal; the second allows wider strips to be used; and the third varies the strip width to optimize the number or length of visible “seams” subject to some restrictions.
Outerstring graphs are the intersection graphs of curves that lie inside a disk such that each curve intersects the boundary of the disk. Outerstring graphs are among the most general classes of intersection graphs studied. To date, no polynomial time algorithm is known for any of the classical graph optimization problems on outerstring graphs; in fact, most are NP-hard. It is known that there is an intersection model for any outerstring graph that consists of polygonal arcs attached to a circle. However, this representation may require an exponential number of segments relative to the size of the graph. Given an outerstring graph and an intersection model consisting of polygonal arcs with a total of N segments, we develop an algorithm that solves the Maximum Weight Independent Set problem in O(N3) time. If the polygonal arcs are restricted to single segments, then outersegment graphs result. For outersegment graphs, we solve the Maximum Weight Independent Set problem in O(n3) time where n is the number of vertices in the graph.
DOI : 10.1016/j.comgeo.2016.05.001 Anahtar Kelimeler :
Outerstring graphs, Maximum weight independent set, Outersegment graphs
ISSN: 0925-7721 Cilt: 60 Sayfa: 19-25
We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile. We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded-capacity dust bin.