We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.

We designed, developed, and studied a visualization, WPHPVis, to support exploration of the Women’s Print History Project (WPHP) data. WPHP are manually-collecting a bibliography that spans the years 1700 to 1836 recording information about books in which women have been involved through a number of roles including as authors, editors, translators, publishers, printers and booksellers. By working directly with WPHP experts to focus on their understanding, and their research practices and needs, we co-designed WPHPVis using interactive construction of network links to support exploration of their data. Through our qualitative study with both experts and non-experts, we learned about how the tool supported the WPHP experts’ research practices as well as about how to improve overall interactive experience. We conclude by discussing the importance of representing missing data, the advantages of striking a balance between visualization structure and explorability, and the opportunities enabled by co-design with domain experts.

We study zombies and survivor, a variant of the game of cops and robber on graphs. In this variant, the single survivor plays the role of the robber and attempts to escape from the zombies that play the role of the cops. The zombies are restricted, on their turn, to always follow an edge of a shortest path towards the survivor. Let $z(G)$ be the smallest number of zombies required to catch the survivor on a graph $G$ with $n$ vertices. We show that there exist outerplanar graphs and visibility graphs of simple polygons such that $z(G) = Θ(n)$. We also show that there exist maximum-degree-$3$ outerplanar graphs such that $z(G) = Ω\left(n/\log(n)\right)$. Let $z_L(G)$ be the smallest number of lazy zombies (zombies that can stay still on their turn) required to catch the survivor on a graph $G$. We establish that lazy zombies are more powerful than normal zombies but less powerful than cops. We prove that $z_L(G) = 2$ for connected outerplanar graphs. We show that $z_L(G)\leq k$ for connected graphs with treedepth $k$. This result implies that $z_L(G)$ is at most $(k+1)\log n$ for connected graphs with treewidth $k$, $O(\sqrt{n})$ for connected planar graphs, $O(\sqrt{gn})$ for connected graphs with genus $g$ and $O(h\sqrt{hn})$ for connected graphs with any excluded $h$-vertex minor. Our results on lazy zombies still hold when an adversary chooses the initial positions of the zombies.

A new parallel algorithm for regular expression matching is developed and applied to the classical grep (global regular expression print) problem. Building on the bitwise data parallelism previously applied to the manual implementation of token scanning in the Parabix XML parser, the new algorithm represents a general solution to the problem of regular expression matching using parallel bit streams. On widely-deployed commodity hardware using 128-bit SSE2 SIMD technology, our algorithm implementations can substantially outperform traditional grep implementations based on NFAs, DFAs or backtracking. 5X or better performance advantage against the best of available competitors is not atypical. The algorithms are also designed to scale with the availability of additional parallel resources such as the wider SIMD facilities (256-bit) of Intel AVX2 or future 512-bit extensions. Our AVX2 implementation showed dramatic reduction in instruction count and significant improvement in speed. Our GPU implementations show further acceleration.

We study nonadaptive broadcasting in trees, a process of sending a message from one vertex in a tree to all other vertices. In the nonadaptive model, each vertex has a specified, ordered list of its neighbors. After receiving a broadcast message, a vertex sends the message to its neighbors, one after another, in the order specified by the list. The broadcast is completed when all vertices have received the message. We obtain lower and upper bounds on the minimum time required to complete a nonadaptive broadcast in a tree and improved upper bounds for general graphs. We give a polynomial time algorithm for determining the minimum nonadaptive broadcast time of any given tree. We also show how to construct the largest possible trees having a given nonadaptive broadcast time. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 157–168 2011

No abstract available.

A spanning subgraph $S = ( V,E^\prime )$ of a connected simple graph $G = ( V,E )$ is a $f( x )$-spanner if for any pair of nodes u and $v $, $d_S ( u,v ) \leq f ( d_G ( u,v ) )$ where $d_G $ and $d_S $ are the usual distance functions in graphs G and S, respectively. The delay of the $f( x )$-spanner is $f( x ) - x$. In this paper $( 2.5\sqrt {( 3x + 6 )/4} + 6 + x )$-spanners for two-dimensional grids with maximum degree 3 are found and it is proven that the delay of these spanners is within a constant factor of optimal. A $( \frac{1}{k}x + k + 8 - \frac{7}{k} + x )$-spanner of the X-tree with maximum degree 3 is described, and it is proven that the delay of this spanner is within a constant factor of optimal. In addition, a $( 2 + x )$-spanner of the pyramid with maximum degree 6 and a $( \frac{1}{k}x + k + 8 - \frac{7}{k} + x )$-spanner of the pyramid with maximum degree 5 are described, and it is proven that the delay of the latter spanner is within a constant factor of optimal.

Abstract A t‐spanner of a network is a subnetwork in which every two nodes that were connected by an edge in the original network are connected by a path of at most t edges in the subnetwork. We present t‐spanners with small maximum or average degree for multidimensional grids. We show how to construct small maximum degree 3‐spanners for d‐dimensional grids for d © 2 and constant average degree 3‐spanners for d‐dimensional grids. We also present t‐spanners of minimum average degree for 2‐dimensional grids. © 1993 by John Wiley & Sons, Inc.

Abstract A spanning subgraph S = (V, E′) of a connected simple graph G = (V, E) is a f(x)‐spanner if for any pair of nodes u and v, dS(u, v) ≦ f(dG(u, v)), where dG and dS are the usual distance functions in graphs G and S, respectively. We are primarily interested in (t + x)‐spanners, which we refer to as additive spanners. We construct low‐degree additive spanners for X‐trees, pyramids, and multidimensional grids. We prove, for arbitrary t > 0, that to determine whether a given graph G has an additive spanner with no more than m edges is NP‐complete. © 1993 by John Wiley & Sons, Inc.

Two points in a polygon are called if the straight line between them lies entirely inside the polygon. The art gallery problem for a polygon P is to find a minimum set of points G in P such that every point in P is visible from some point of G. The author provides an introduction to art gallery theorems and surveys the recent results of the field. The emphasis is on the results rather than the techniques. Several new problems that have the same geometric flavor as art gallery problems are also examined.>