Maximizing the guarded boundary of an Art Gallery is APX-complete

In the Art Gallery problem, given is a polygonal gallery and the goal is to guard the gallery's interior or walls with a number of guards that must be placed strategically in the interior, on walls or on corners of the gallery. Here we consider a more realistic version: exhibits now have size and may have different costs. Moreover the meaning of guarding is relaxed: we use a new concept, that of watching an expensive art item, i.e. overseeing a part of the item. The main result of the paper is that the problem of maximizing the total value of a guarded weighted boundary is APX-complete. This is shown by an appropriate ‘gap-preserving’ reduction from the Max-5-occurrence-3-Sat problem. We also show that this technique can be applied to a number of maximization variations of the art gallery problem. In particular we consider the following problems: given a polygon with or without holes and k available guards, maximize a) the length of walls guarded and b) the total cost of paintings watched or overseen. We prove that all the above problems are APX-complete.     

Vertex covers and eternal dominating sets

The eternal domination problem requires a graph to be protected against an infinitely long sequence of attacks on vertices by guards located at vertices, the configuration of guards inducing a dominating set at all times. An attack at a vertex with no guard is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow any number of guards to move to neighboring vertices at the same time in response to an attack. We compare the eternal domination number with the vertex cover number of a graph. One of our main results is that the eternal domination number is less than the vertex cover number of any graph of minimum degree at least two having girth at least nine.     

Graphs with equal eternal vertex cover and eternal domination numbers

Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. If attacks occur at vertices, this is known at the eternal domination problem. If attacks occur at edges, this is known as the eternal vertex cover problem. We focus on the model in which all guards can move to neighboring vertices in response to an attack. Motivated by the question of which graphs have equal eternal vertex cover and eternal domination numbers, a number of results are presented; one of the main results of the paper is that the eternal vertex cover number is greater than the eternal domination number (in the all-guards move model) in all graphs of minimum degree at least two.     

Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

We present an optimal Θ(n)-time algorithm for the selection of a subset of the vertices of an n-vertex plane graph G so that each of the faces of G is covered by (i.e., incident with) one or more of the selected vertices. At most n/2 vertices are selected, matching the worst-case requirement. Analogous results for edge-covers are developed for two different notions of “coverage”. In particular, our linear-time algorithm selects at most n−2 edges to strongly cover G, at most n/3 diagonals to cover G, and in the case where G has no quadrilateral faces, at most n/3 edges to cover G. All these bounds are optimal in the worst-case. Most of our results flow from the study of a relaxation of the familiar notion of a 2-coloring of a plane graph which we call a face-respecting 2-coloring that permits monochromatic edges as long as there are no monochromatic faces. Our algorithms apply directly to the location of guards, utilities or illumination sources on the vertices or edges of polyhedral terrains, polyhedral surfaces, or planar subdivisions.     

A problem of the bending of a plate for a doubly connected domain with a partially unknown boundary

The problem of the bending of an isotropic elastic plate, bounded by two rectangles with vertices lying on the same half-line, drawn from the common centre, is considered. The vertices of the inner rectangle are cut by convex smooth arcs (we will call the set of these arcs the unknown part of the boundary). It is assumed that normal bending moments act on each rectilinear section of the boundary contours in such a way that the angle of rotation of the midsurface of the plate is a piecewise-constant function. The unknown part of the boundary is free from external forces. The problem consists of determining the bending of the midsurface of the plate and the analytic form of the unknown part of the boundary when the tangential normal moment acting on it takes a constant value, while the shearing force and the normal bending moments and torques are equal to zero. The problem is solved by the methods of the theory of boundary-value problems of analytical functions.     

On a straight-line embedding problem of graphs

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane in general position. A straight-line embedding of G onto P is an embedding of G onto whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.     

Cellular Chain Complex of Small Covers with Integer Coefficients and Its Application

Let Pⁿ be a simple n-polytope with a Z²-characteristic function λ. And h is a Morse function over Pⁿ. Then the small cover Mⁿ(λ) corresponding to the pair (Pⁿ, λ) has a cell structure given by h. From this cell structure we can derive a cellular chain complex of Mⁿ(λ) with integer coefficients. In this paper, firstly, we discuss the highest dimensional boundary morphism ∂_n of this cellular chain complex and get that ∂_n=0 or 2 by a natural way. And then, from the well-known result that the submanifold corresponding to (F, λ_F) is naturally a small cover with dimension k, where F is any k-face of Pⁿ and λ_F is the restriction of λ on F, we get that ∂_k=0 or ±2 for 0 ≤ k < n. Finally, by using the definition of inherited characteristic function which is the restriction of λ on the faces of Pⁿ, we get a way to calculate the homology groups of Mⁿ(λ). Applying our result to a 3-small cover we have that the homology groups of any 3-small cover is torsion-free or has only 2-torsion.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

Covering hypercubes by isometric paths

An isometric path is merely any shortest path between two vertices. If the vertices of the hypercube Q_n are represented by the set of 0–1 vectors of length n, an isometric path is obtained by changing the coordinates of a vector one at a time, never changing the same coordinate more than once. The minimum number of isometric paths required to cover the vertices of Q_n is at least 2ⁿ/(n+1). We show that when n+1 is a power of 2, the lower bound is in fact the minimum. In doing so, we construct a family of disjoint isometric paths which can be used to find an upper bound for additional classes of hypercubes.     

Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G'sbipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d(K_n) = [log₂n], η(K_n) = d(K_n) for n 16, and η(K_n) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.     

Edge guards for the fortress problem

The fortress problem is one of determining a set of guards to cover the exterior of a simple polygon. O'Rourke and Wood [cited in 7] showed that vertex guards are sometimes necessary and always sufficient for an -vertex polygon. In this paper, we solve the same problem for edge guards. Tight bounds of and edge guards are obtained for general and rectilinear polygons, respectively. Received 19 June 1999; in revised form 23 March 2000.     

Three problems about simple polygons

We give three related algorithmic results concerning a simple polygon P:

1. Improving a series of previous work, we show how to find a largest pair of disjoint congruent disks inside P in linear expected time.

2. As a subroutine for the above result, we show how to find the convex hull of any given subset of the vertices of P in linear worst-case time.

3. More generally, we show how to compute a triangulation of any given subset of the vertices or edges of P in almost linear time.

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

Foolproof eternal domination in the all-guards move model

The eternal domination problem requires a graph be protected against an infinitely long sequence of attacks at vertices, by guards located at vertices, with the requirement that the configuration of guards induces a dominating set at all times. An attack is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow all guards to move to neighboring vertices in response to an attack, but allow the attacked vertex to choose which neighboring guard moves to the attacked vertex. This is the all-guards move version of the ??foolproof?? eternal domination problem that has been previously studied. We present some results and conjectures on this problem.     

Least domination in a graph

The least domination number γ_L of a graph G is the minimum cardinality of a dominating set of G whose domination number is minimum. The least point covering number _L of G is the minimum cardinality of a total point cover (point cover including every isolated vertex of G) whose total point covering number is minimum. We prove a conjecture of Sampathkumar saying that in every connected graph of order n 2. We disprove another one saying that γ_{L L} in every graph but instead of it, we establish the best possible inequality . Finally, in relation with the minimum cardinality γ_t of a dominating set without isolated vertices (total dominating set), we prove that the ratio γ_L/γ_t can be in general arbitrarily large, but remains bounded by if we restrict ourselves to the class of trees.     

Boundary labeling: Models and efficient algorithms for rectangular maps

We introduce boundary labeling, a new model for labeling point sites with large labels. According to the boundary-labeling model, labels are placed around an axis-parallel rectangle that contains the point sites, each label is connected to its corresponding site through a polygonal line called leader, and no two leaders intersect. Although boundary labeling is commonly used, e.g., for technical drawings and illustrations in medical atlases, this problem has not yet been studied in the literature. The problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem.

In this paper we investigate several variants of the boundary-labeling problem. We consider labels of identical or different size, straight-line or rectilinear leaders, fixed or sliding ports for attaching leaders to sites and attaching labels to one, two or all four sides of the bounding rectangle. For any variant of the boundary labeling model, we aim at highly esthetical placements of labels and leaders. We present simple and efficient algorithms that minimize the total leader length or, in the case of rectilinear leaders, the total number of bends.     

Rotationally optimal spanning and Steiner trees in uniform orientation metrics

We consider the problem of finding a minimum spanning and Steiner tree for a set of n points in the plane where the orientations of edge segments are restricted to λ uniformly distributed orientations, λ=2,3,4,… , and where the coordinate system can be rotated around the origin by an arbitrary angle. The most important cases with applications in VLSI design arise when λ=2 or λ=4. In the former, so-called rectilinear case, the edge segments have to be parallel to one of the coordinate axes, and in the latter, so-called octilinear case, the edge segments have to be parallel to one of the coordinate axes or to one of the lines making 45° with the coordinate axes (so-called diagonals). As the coordinate system is rotated—while the points remain stationary—the length and indeed the topology of the minimum spanning or Steiner tree changes. We suggest a straightforward polynomial-time algorithm to solve the rotational minimum spanning tree problem. We also give a simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting, and a finite time algorithm for the general Steiner tree problem with λ uniform orientations. Finally, we provide some computational results indicating the average savings for different values of n and λ both for spanning and Steiner trees.     

On fat partitioning, fat covering and the union size of polygons

The complexity of the contour of the union of simple polygons with n vertices in total can be O(n²) in general. A notion of fatness for simple polygons is introduced that extends most of the existing fatness definitions. It is proved that a set of fat polygons with n vertices in total has union complexity O(n log log n), which is a generalization of a similar result for fat triangles (Matou ek et al., 1994). Applications to several basic problems in computational geometry are given, such as efficient hidden surface removal, motion planning, injection molding, and more. The result is based on a new method to partition a fat simple polygon P with n vertices into O(n) fat convex quadrilaterals, and a method to cover (but not partition) a fat convex quadrilateral with O(l) fat triangles. The maximum overlap of the triangles at any point is two, which is optimal for any exact cover of a fat simple polygon by a linear number of fat triangles.     

Improved Approximation for Guarding Simple Galleries from the Perimeter

We provide an O(log?log?opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size \(O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})\) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log?opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.