Given a set S of n points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in S to its closest line. We present a (1+ε)-approximation algorithm for the two-line-center problem that runs in O((n/ε) log (1/ε)) time, which improves the previously best O(nlog n + (n/ε²) log (1/ε) + (1/ε³)log (1/ε))-time algorithm. We also consider three variants of this problem, in which the orientations of the two lines are restricted: (1) the orientation of one of the two lines is fixed, (2) the orientations of both lines are fixed, and (3) the two lines are required to be parallel. For each of these three variants, we give the first (1+ε)-approximation algorithm that runs in linear time. In particular, for the variant where the orientation of one of the two lines is fixed, we also give an improved exact algorithm that runs in O(n log n) time and show that it is optimal.

Oriented spanners were presented at ESA'23 as an extension of the well-researched geometric spanners: Given a set P of points in a metric space and an oriented graph G, the oriented dilation of two points p,q ∈ P is the length of the shortest closed walk in G containing p and q divided by the minimum perimeter triangle of p and q. G is called a t-spanner, if the maximum dilation over all pairs of points in P is at most t. This paper presents the first constructions of sparse oriented spanners for metric spaces beyond the Euclidean space. Given an orientation of the complete graph (i.e. a tournament) with dilation t on n points that satisfies an additional short-cycle property, we show how to extract a (t+ε)-spanner with 𝒪(k) edges in 𝒪(kn²+T(n)) time, for any metric space admitting a well-separated pair decomposition with k pairs computable in T(n) time. We supplement this with an improved construction of tournaments for metric point sets, obtaining dilation 5/3. This improves the previous bound of 2 and approaches the lower bound of 1.5. Combined, for n points in a metric space with constant doubling dimension d, this yields a (5/3 + ε)-spanner with (1/ε)^{𝒪(d)}n edges computable in (1/ε)^𝒪(d) n³ time using 𝒪(n²) space. This improves the dilation over the (2+ε)-spanner for Euclidean point sets presented at SoCG’25 while applying to more general metric spaces. Moreover, we generalize the known (2+ε)-spanner to doubling spaces. In particular, an oriented (2+ε)-spanner with 𝒪(ε^{-d} n) edges can be constructed in (1/ε)^𝒪(d) n log n time using 𝒪(ε^{-d} n) space. Since the oriented dilation can be dominated by one pair of points, we also consider the oriented average dilation, which is the sum over the oriented dilation of all pairs of points divided by the number of pairs. While oriented (1+ε)-spanners do not exist for every point set, we present an algorithm that computes a spanner with average dilation 1+ε for point sets in a metric space of constant doubling dimension d: More concretely, our algorithm computes an oriented spanner with average dilation at most 1 + 𝒪(1/s) + s^𝒪(d)/n with s^𝒪(d) n edges in s^𝒪(d) n log n time using s^𝒪(d) n space, where s is any sufficiently large number that may depend on n.

A connected graph has a ( k , ℓ ) -cover if each of its edges is contained in at least ℓ cliques of order k . Motivated by recent advances in extremal combinatorics and the literature on edge modification problems, we study the algorithmic version of the ( k , ℓ ) -cover problem. Given a connected graph G , the ( k , ℓ ) -cover problem is to identify the smallest subset of non-edges of G such that their addition to G results in a graph with a ( k , ℓ ) -cover. For every constant k ≥ 3 , we show that the ( k , 1 ) -cover problem is NP -complete for general graphs. Moreover, we show that for every constant k ≥ 3 , the ( k , 1 ) -cover problem admits no polynomial-time constant-factor approximation algorithm unless P = NP . However, we show that the ( 3 , 1 ) -cover problem can be solved in polynomial time when the input graph is chordal. For the class of trees and general values of k , we show that the ( k , 1 ) -cover problem is NP -hard even for spiders. However, we show that for every k ≥ 4 , the ( 3 , k − 2 ) -cover and the ( k , 1 ) -cover problems are constant-factor approximable when the input graph is a tree.

A hypergraph $H$ consists of a set $V$ of vertices and a set $E$ of hyperedges that are subsets of $V$. A $t$-tuple of $H$ is a subset of $t$ vertices of $V$. A $t$-tuple $k$-coloring of $H$ is a mapping of its $t$-tuples into $k$ colors. A coloring is called $(t,k,f)$-polychromatic if each hyperedge of $E$ that has at least $f$ vertices contains tuples of all the $k$ colors. Let $f_H(t,k)$ be the minimum $f$ such that $H$ has a $(t,k,f)$-polychromatic coloring. For a family of hypergraphs $\cal{H}$ let $f_{\cal{H}}(t,k)$ be the maximum $f_H(t,k)$ over all hypergraphs $H$ in $\cal{H}$. We present several bounds on $f_{\cal{H}}(t,k)$ for $t\ge 2$. - Let $\cal{H}$ be the family of hypergraphs $H$ that is obtained by taking any set $P$ of points in $\Re^2$, setting $V:=P$ and $E:=\{d\cap P\colon d\text{ is a disk in }\Re^2\}$. We prove that $f_\cal{H}(2,k)\le 3.7^k$, that is, the pairs of points (2-tuples) can be $k$-colored such that any disk containing at least $3.7^k$ points has pairs of all colors. - For the family $\mathcal{H}$ of shrinkable hypergraphs of VC-dimension at most $d$ we prove that $ f_\cal{H}(d{+}1,k) \leq c^k$ for some constant $c=c(d)$. We also prove that every hypergraph with $n$ vertices and with VC-dimension at most $d$ has a $(d{+}1)$-tuple $T$ of depth at least $\frac{n}{c}$, i.e., any hyperedge that contains $T$ also contains $\frac{n}{c}$ other vertices. - For the relationship between $t$-tuple coloring and vertex coloring in any hypergraph $H$ we establish the inequality $\frac{1}{e}\cdot tk^{\frac{1}{t}}\le f_H(t,k)\le f_H(1,tk^{\frac{1}{t}})$. For the special case of $k=2$, we prove that $t+1\le f_H(t,2)\le\max\{f_H(1,2), t+1\}$; this improves upon the previous best known upper bound. - We generalize some of our results to higher dimensions, other shapes, pseudo-disks, and also study the relationship between tuple coloring and epsilon nets.

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.

Given a point set P in a metric space and a real number t ≥ 1, an oriented t-spanner is an oriented graph G = (P, E), where for every pair of distinct points p and q in P, the shortest oriented closed walk in G that contains p and q is at most a factor t longer than the perimeter of the smallest triangle in P containing p and q. The oriented dilation of a graph G is the minimum t for which G is an oriented t-spanner. For arbitrary point sets of size n in ℝ^d, where d ≥ 2 is a constant, the only known oriented spanner construction is an oriented 2-spanner with binom(n,2) edges. Moreover, there exists a set P of four points in the plane, for which the oriented dilation is larger than 1.46, for any oriented graph on P. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of n points in ℝ^d, where d is a constant, we construct an oriented (2+ε)-spanner with 𝒪(n) edges in 𝒪(n log n) time and 𝒪(n) space. Our construction uses the well-separated pair decomposition and an algorithm that computes a (1+ε)-approximation of the minimum-perimeter triangle in P containing two given query points in 𝒪(log n) time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the oriented graph is already given, computing its oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in ℝ^d, where d is a constant.

Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known.

Cops and Robbers is a type of pursuit-evasion game played on a graph where a set of cops try to capture a single robber. The cops first choose their initial vertex positions, and later the robber chooses a vertex. The cops and robbers make their moves in alternate turns: in the cops' turn, every cop can either choose to move to an adjacent vertex or stay on the same vertex, and likewise the robber in his turn. If the cops can capture the robber in a finite number of rounds, the cops win, otherwise the robber wins. The cop-number of a graph is the minimum number of cops required to catch a robber in the graph. It has long been known that graphs embedded on surfaces (such as planar graphs and toroidal graphs) have a small cop-number. Recently, Durocher et al. [Graph Drawing, 2023] investigated the problem of cop-number for the class of 1-planar graphs, which are graphs that can be embedded in the plane such that each edge is crossed at most once. They showed that unlike planar graphs which require just three cops, 1-planar graphs have an unbounded cop-number. On the positive side, they showed that maximal 1-planar graphs require only three cops by crucially using the fact that the endpoints of every crossing in an embedded maximal 1-planar graph induce a K 4 . In this paper, we show that the cop-number remains bounded even under the relaxed condition that the endpoints induce at least three edges. More precisely, let an ×-crossing of an embedded 1-planar graph be a crossing whose endpoints induce a matching; i.e., there is no edge connecting the endpoints apart from the crossing edges themselves. We show that any 1-planar graph that can be embedded without ×-crossings has cop-number at most 21. Moreover, any 1-planar graph that can be embedded with at most γ ×-crossings has cop-number at most γ + 21 .

In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph G, consisting of a vertex set V(G) of size n and an edge set E(G). Each vertex in V(G) is assigned a color from the set {1,2,…, c}. The objective is to determine a subset V' ⊆ V(G) with minimum possible cardinality, such that for every vertex v ∈ V(G), at least one of its nearest neighbors in V' (measured in terms of the hop distance) shares the same color as v. The decision problem, indicating whether there exists a subset V' of cardinality at most l for some positive integer l, is known to be NP-complete even for planar graphs. In this paper, we establish that the MCS problem is NP-complete on trees. We also provide a fixed-parameter tractable (FPT) algorithm for MCS on trees parameterized by the number of colors (c) running in O(2^{6c} n^6) time, significantly improving the currently best-known algorithm whose running time is O(2^{4c} n^{2c+3}). In an effort to comprehensively understand the computational complexity of the MCS problem across different graph classes, we extend our investigation to interval graphs. We show that it remains NP-complete for interval graphs, thus enriching graph classes where MCS remains intractable.

Let T be a tessellation composed of equilateral triangular regions, where each region has an associated positive weight. We present two methods that discretize the space based on the placement of Steiner points in the cells of T. Using such a discretization, we can use Dijkstra's algorithm for computing the shortest path in the geometric graph obtained. This will lead us to two approximation algorithms for solving the Weighted Region Problem. For a given parameter ε∈(0,1], the first discretization scheme provides an approximate path that is (1+0.428ε) times better than the approximation given by Aleksandrov et al. [Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM, 52(1):25-53, 2005]. The other discretization scheme uses at least (ε+2ε+4ε+4)log2⁡e fewer points per segment of the triangulation with the same approximation factor.

We consider a variant of the art gallery problem where all guards are limited to seeing 180degree. Guards that can only see in one direction are called half-guards. We give a polynomial time approximation scheme for vertex guarding the vertices of a weakly-visible polygon with half-guards. We extend this to vertex guarding the boundary of a weakly-visible polygon with half-guards. We also show NP-hardness for vertex guarding a weakly-visible polygon with half-guards. Lastly, we show that the orientation of half-guards is critical in terrain guarding. Depending on the orientation of the half-guards, the problem is either very easy (polynomial time solvable) or very hard (NP-hard).

Given two sets $S$ and $T$ of points in the plane, of total size $n$, a {many-to-many} matching between $S$ and $T$ is a set of pairs $(p,q)$ such that $p\in S$, $q\in T$ and for each $r\in S\cup T$, $r$ appears in at least one such pair. The {cost of a pair} $(p,q)$ is the (Euclidean) distance between $p$ and $q$. In the {minimum-cost many-to-many matching} problem, the goal is to compute a many-to-many matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimum-weight edge cover in a bipartite graph, and hence can be solved in $O(n^3)$ time. In a more restricted setting where all the points are on a line, the problem can be solved in $O(n\log n)$ time [Colannino, Damian, Hurtado, Langerman, Meijer, Ramaswami, Souvaine, Toussaint; Graphs Comb., 2007]. However, no progress has been made in the general planar case in improving the cubic time bound. In this paper, we obtain an $O(n^2\cdot poly(\log n))$ time exact algorithm and an $O( n^{3/2}\cdot poly(\log n))$ time $(1+ε)$-approximation in the planar case. Our results affirmatively address an open problem posed in [Colannino et al., Graphs Comb., 2007].

In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ 2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2 r opt at any query time, where r opt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O(log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2.

We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.

We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP-hard even when all the rectangles are "anchored" at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any $ε>0$, there exists a $(2+ε)$-approximation algorithm for the MDS problem on "diagonal-anchored" rectangles, providing the first $O(1)$-approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on "diagonal-anchored" rectangles is the same as the MDS problem on "diagonal-anchored" L-frames: the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a $(2+ε)$-approximation for the problem with "diagonal-anchored" L-frames. On the other hand, we show that the problem is APX-hard in case the input L-frames intersect the diagonal, or the horizontal segments of the L-frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L-frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called "edge intersection model" and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).

A pseudo-polynomial time $(1 + \varepsilon)$-approximation algorithm is presented for computing the integral and average Fréchet distance between two given polygonal curves $T_1$ and $T_2$. In particular, the running time is upper-bounded by $\mathcal{O}( ζ^{4}n^4/\varepsilon^{2})$ where $n$ is the complexity of $T_1$ and $T_2$ and $ζ$ is the maximal ratio of the lengths of any pair of segments from $T_1$ and $T_2$. The Fréchet distance captures the minimal cost of a continuous deformation of $T_1$ into $T_2$ and vice versa and defines the cost of a deformation as the maximal distance between two points that are related. The integral Fréchet distance defines the cost of a deformation as the integral of the distances between points that are related. The average Fréchet distance is defined as the integral Fréchet distance divided by the lengths of $T_1$ and $T_2$. Furthermore, we give relations between weighted shortest paths inside a single parameter cell $C$ and the monotone free space axis of $C$. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.

Let S be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane frac{3+4 pi}{3}-spanner of S whose vertex degree is at most 3. Let Lambda be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane 3 sqrt{2}-spanner for Lambda whose vertex degree is at most 3. For points that are in the plane and in general position, we show how to compute plane degree-3 spanners with a linear number of Steiner points.

We propose a new measure to capture similarity between polygonal curves, called the minimum backward Fréchet distance. It is a natural optimization on the weak Fréchet distance, a variant of the well-known Fréchet distance. More specifically, for a given threshold ε, we are searching for a pair of walks for two entities on the two input curves, T1 and T2, such that the union of the portions of backward movements is minimized and the distance between the two entities, at any time during the walk, is less than or equal to ε. Our algorithm detects if no such pair of walks exists. This natural optimization problem appears in many applications in Geographical Information Systems, mobile networks and robotics. We provide an exact algorithm with time complexity of O(n2 log n) and space complexity of O(n2), where n is the maximum number of segments in the input polygonal curves.

We propose designing data structures called succinct geometric indexes of negligible space (more precisely, o ( n ) bits) that support geometric queries in optimal time, by taking advantage of the n points in the dataset permuted and stored elsewhere as a sequence. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O (lg n ) time. We also design three variants of this index. The first supports point location using lg n + 2√lg n + O (lg 1/4 n ) point-line comparisons. The second supports point location in o (lg n ) time when the coordinates are integers bounded by U . The last variant can answer point location queries in O ( H + 1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy O ( n ) words or O(n lg n ) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in O (lg 2 n ) time.

The phylogenetic diversity (PD) of a set of species is a measure of their evolutionary distinctness based on a phylogenetic tree. PD is increasingly being adopted as an index of biodiversity in ecological conservation projects. The Noah's Ark Problem (NAP) is an NP-Hard optimization problem that abstracts a fundamental conservation challenge in asking to maximize the expected PD of a set of taxa given a fixed budget, where each taxon is associated with a cost of conservation and a probability of extinction. Only simplified instances of the problem, where one or more parameters are fixed as constants, have as of yet been addressed in the literature. Furthermore, it has been argued that PD is not an appropriate metric for models that allow information to be lost along paths in the tree. We therefore generalize the NAP to incorporate a proposed model of feature loss according to an exponential distribution and term this problem NAP with Loss (NAPL). In this paper, we present a pseudopolynomial time approximation scheme for NAPL.

We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that support geometric queries in optimal time, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O(lg n) time. We also design three variants of this index. The first supports point location using point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location queries in O(H + 1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy O(n) words or O(n lg n) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in O(lg2 n) time.

We address the following problem: Given a complete k-partite geometric graph K whose vertex set is a set of n points in $\mathbb{R}^d$, compute a spanner of K that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a $(5+\epsilon)$-spanner of K with $O(n)$ edges in $O(n\log n)$ time. The second algorithm computes a $(3+\epsilon)$-spanner of K with $O(n\log n)$ edges in $O(n \log n)$ time. The latter result is optimal: We show that for any $2\leq k\leq n-\Theta(\sqrt{n\log n})$, spanners with $O(n\log n)$ edges and stretch factor less than 3 do not exist for all complete k-partite geometric graphs.

We present I/O-efficient algorithms for computing optimal separator partitions of planar graphs. Our main result shows that, given a planar graph G with N vertices and an integer $r > 0$, a vertex separator of size O$(N / \sqrt{r})$ that partitions G into O$(N / r)$ subgraphs of size at most r and boundary size O$(\sqrt{r})$ can be computed in O$(\operatorname{sort}(N))$ I/Os. This bound holds provided that $M \ge 56r \log^2 B$. Together with an I/O-efficient planar embedding algorithm presented in [N. Zeh, I/O-Efficient Algorithms for Shortest Path Related Problems, Ph.D. thesis, School of Computer Science, Carleton University, Ottawa, ON, Canada, 2002], this result is the basis for I/O-efficient solutions to many other fundamental problems on planar graphs, including breadth-first search and shortest paths [L. Arge, G. S. Brodal, and L. Toma, J. Algorithms, 53 (2004), pp. 186–206; L. Arge, L. Toma, and N. Zeh, I/O-efficient algorithms for planar digraphs, in Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2003, pp. 85–93], depth-first search [L. Arge et al., J. Graph Algorithms Appl., 7 (2003), pp. 105–129; L. Arge and N. Zeh, I/O-efficient strong connectivity and depth-first search for directed planar graphs, in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2003, pp. 261–270], strong connectivity [L. Arge and N. Zeh, I/O-efficient strong connectivity and depth-first search for directed planar graphs, in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2003, pp. 261–270], and topological sorting [L. Arge and L. Toma, Simplified external memory algorithms for planar DAGs, in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Comput. Sci. 3111, Springer-Verlag, Berlin, New York, 2004, pp. 493–503; L. Arge, L. Toma, and N. Zeh, I/O-efficient algorithms for planar digraphs, in Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2003, pp. 85–93]. Our second result shows that, given I/O-efficient solutions to these problems, a general separator algorithm for graphs with costs and weights on their vertices [L. Aleksandrov et al., Partitioning planar graphs with costs and weights, in Proceedings of the 4th Workshop on Algorithm Engineering and Experiments, Lecture Notes in Comput. Sci. 2409, Springer-Verlag, Berlin, New York, 2002, pp. 98–107] can be made I/O-efficient. Many classical separator theorems are special cases of this result. In particular, our I/O-efficient version allows the computation of a separator as produced by our first separator algorithm, but without placing any constraints on r in relation to the memory size.

We present the first parallel algorithm for building a Hausdorff Voronoi diagram (HVD). Our algorithm is targeted towards cluster computing architectures and computes the Hausdorff Voronoi diagram for non-crossing objects in time O((n log4n)/p) for input size n and p processors. In addition, our parallel algorithm also implies a new sequential HVD algorithm that constructs HVDs for non-crossing objects in time O(n log4n). This improves on previous sequential results and solves an open problem posed by Papadopoulou and Lee (2004)

In this article, we present an approximation algorithm for solving the single source shortest paths problem on weighted polyhedral surfaces. We consider a polyhedral surface P as consisting of n triangular faces, where each face has an associated positive weight. The cost of travel through a face is the Euclidean distance traveled, multiplied by the face's weight. For a given parameter ε, 0 <ε < 1, the cost of the computed paths is at most 1 + ε times the cost of corresponding shortest paths. Our algorithm is based on a novel way of discretizing polyhedral surfaces and utilizes a generic greedy approach for computing shortest paths in geometric graphs obtained by such discretization. Its running time is O(C(P) n /√ε log n /ε log 1/ε) time, where C(P) captures geometric parameters and the weights of the faces of P .

We consider the classical geometric problem of determining a shortest path through a weighted domain.We present approximation algorithms that compute e-short paths, i.e., paths whose costs are within a factor of 1 + e of the shortest path costs, for an arbitrary constant e > O, for the following geometric configurations: O n 1 1 runs in (~ log ; (~ +log n)) time.The run time improves to O(;~-log ~logn)) when all weights are equal.This can be used to solve the shortest path problem amidst obstacles in 3-dimensional Euclidean space (ESP-3D).

External memory (EM) algorithms are designed for computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size.Block-wise access to data is a central theme in the design of efficient EM algorithms.A similar requirement arises in the transmission of data between processors in certain parallel computation models such as BSP* and CGM, for which block-wise communication is a crucial issue.We consider multisearch problems, where a large number of queries are to be simultaneously processed and satisfied by navigating through large data structures on parallel computers.The examples used originate as BSP* algorithms and we adapt them to the EM situation where the queries and data structure are considered to be much larger than the size of the available internal memory.This paper presents techniques to achieve blocking for I/O as well as for communication in multisearch on the BSP* and EM-BSP* models.In the area of EM algorithms new algorithms for multisearch in balanced trees are described.For search trees up to size O(n log n) where n is the number of queries, we obtain work-optimal, parallel, EM multisearch algorithms whose I/O and communication time are the same, asymptotically, as the computation time.These algorithms are obtained via the simulation technique of (151.For larger trees we describe a parallel, EM algorithm which is simultaneously c-optimal and I/O-optimal.We give a lower bound to the number of I/O operations required for filtering n queries through a binary or multiway search tree of size m when m 2 n'+', constant E > 0.

Consider a simple polyhedron P, possibly non-convex, composed of n triangular regions (faces), each assigned a positive weight indicating the cost of travel in that region. We present and experimentally study several algorithms to compute an approximate weighted geodesic shortest path, ß 0 (s; t), between two points s and t on the surface of P. Our algorithms are simple, practical, less prone to numerical problems, adaptable to a wide spectrum of weight functions, and use only elementary data structures. An additional feature of our algorithms is that execution time and space utilization can be traded off for accuracy; likewise, a sequence of approximate shortest paths for a given pair of points can be computed with increasing accuracy (and execution time) if desired. Dynamic changes to the polyhedron (removal, insertions of vertices or faces) are easily handled. The key step in these algorithms is the construction of a graph by introducing Steiner points on the edges of the given p...

No abstract available.

A sequence d of integers is a degree sequence if there exists a (simple) graph G such that the components of d are equal to the degrees of the vertices of G. The graph G is said to be a realization of d. We provide an efficient parallel algorithm to realize d; the algorithm runs in $O(\log n)$ time using $O(n + m)$ CRCW PRAM processors, where n and m are the number of vertices and edges in G. Before our result, it was not known if the problem of realizing d is in $NC$.

Complex organizations are characterized by distributed decision making, and require a sharing of perspectives among distributed decision makers if they are to coordinate activity and adapt to changing circumstances. This paper explains the process of perspective taking and its roles in human communication, mutual trust, and organizational learning. SPIDER is a software environment for enriching communication among managers by improving their ability to represent and exchange understandings of the situations they face. Cognitive maps linked to underlying assumptions are used as a basis for sharing their perspectives and enabling coordination of distributed decision making.