We study two fundamental geometric problems on a dynamic set of n axis-parallel boxes in d-dimensional space. The maximum depth problem asks for the largest number of boxes that contain a common point, whereas Klee’s measure problem asks for the volume of the union of the boxes. We present fully dynamic exact data structures for both problems achieving Õ(n^{(d-1)/2}) amortized update time. This update time is optimal for an exact dynamic algorithm, up to logarithmic factors, assuming the Combinatorial k-Clique Hypothesis. Previously, matching bounds were established only for d = 1 [Imai and Asano, J. Algo.'83], and for d = 2 [Suri, Xue, Yang, and Zhu, SoCG'25]. Our approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell. This argument allows us to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates. We believe this technique may be of independent interest for other dynamic geometric problems.

Let G = (V,E) be a directed graph on n vertices where each vertex has out-degree k. We say that G is kNN-realizable in d-dimensional Euclidean space if there exists a point set P = {p_1, p_2, …, p_n} in ℝ^d along with a one-to-one mapping ϕ: V → P such that for any u,v ∈ V, u is an out-neighbor of v in G if and only if ϕ(u) is one of the k nearest neighbors of ϕ(v); we call the map ϕ a kNN-realization of G in ℝ^d. The kNN-realization problem, which aims to compute a kNN-realization of an input graph in ℝ^d, is known to be NP-hard already for d = 2 and k = 1 [Eades and Whitesides, Theoretical Computer Science, 1996], and to the best of our knowledge has not been studied in dimension d = 1. The main results of this paper are the following: - For any fixed dimension d ≥ 2, we can efficiently compute an embedding realizing at least a 1 - ε fraction of G’s edges, or conclude that G is not kNN-realizable in ℝ^d. - For d = 1, we can decide in O(kn) time whether G is kNN-realizable and, if so, compute a realization in O(n^{2.5} poly(log n)) time.

Abstract. Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirements) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in one and two dimensions, which significantly improve and extend the previous results. Our results include the following: (1) The first data structure for [Formula: see text]-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of [Formula: see text], improving the [Formula: see text] bound of Agarwal et al. [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020, 27; ACM Trans. Algorithms, 18 (2022), 40], where [Formula: see text] denotes an arbitrarily small constant. (2) A data structure for [Formula: see text]-approximate dynamic unit-square set cover with [Formula: see text] amortized update time, substantially improving the [Formula: see text] update time of Agarwal et al. (3) A data structure for [Formula: see text]-approximate dynamic square set cover with [Formula: see text] randomized amortized update time, improving the [Formula: see text] update time of Chan and He [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020; J. Comput. Geom., 13 (2022), pp. 90–114]. (4) A data structure for [Formula: see text]-approximate dynamic two-dimensional half-plane set cover with [Formula: see text] randomized amortized update time. The previous solution for a half-plane set cover by Chan and He [ Proceedings of the 37 th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 189, Schloss Dagstuhl - Leibniz Center for Informatics, 2021, 25; J. Comput. Geom., 13 (2022), pp. 90–114] is slower and can only report the size of the approximate solution. (5) The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for [Formula: see text]-approximate dynamic weighted interval set cover with [Formula: see text] amortized update time and a data structure for [Formula: see text]-approximate dynamic weighted unit-square set cover with [Formula: see text] amortized update time.

In the committee selection problem, the goal is to choose a subset of size $k$ from a set of candidates $C$ that collectively gives the best representation to a set of voters. We consider this problem in Euclidean $d$-space where each voter/candidate is a point and voters' preferences are implicitly represented by Euclidean distances to candidates. We explore fault-tolerance in committee selection and study the following three variants: (1) given a committee and a set of $f$ failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of $f$ candidates; and (3) design a committee with the best replacement score under worst-case failures. The score of a committee is determined using the well-known (min-max) Chamberlin-Courant rule: minimize the maximum distance between any voter and its closest candidate in the committee. Our main results include the following: (1) in one dimension, all three problems can be solved in polynomial time; (2) in dimension $d \geq 2$, all three problems are NP-hard; and (3) all three problems admit a constant-factor approximation in any fixed dimension, and the optimal committee problem has an FPT bicriterion approximation.

Suppose we are given a pair of points $s, t$ and a set $S$ of $n$ geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph $G$ with vertex set $S$ and every edge labeled from $\{0, 1\}$, such that a set $S_d \subseteq S$ of obstacles separates $s$ from $t$ if and only if $G[S_d]$ contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-Removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a $2.3146^qn^{O(1)}$ algorithm for Obstacle-Removal, significantly improving upon the previously best known $q^{O(q^3)} n^{O(1)}$ algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-Removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-Separation problem, the input consists of the set S of obstacles, a point set A of k points and p pairs $(s_1, t_1),... (s_p, t_p)$ of points from A. The task is to find a minimum subset $S_r \subseteq S$ such that for every $i$, every curve from $s_i$ to $t_i$ intersects at least one obstacle in $S_r$. We obtain $2^{O(p)} n^{O(k)}$-time algorithm for Generalized Points-Separation problem. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where $(s_1, t_1), ... (s_p, t_p)$ contains all the pairs of points in A. Finally, we improve the running time of our algorithm to $f(p,k) n^{O(\sqrt{k})}$ when the obstacles are unit disks, where $f(p,k) = 2^O(p) k^{O(k)}$, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on $k$ of our algorithms is essentially optimal.

We consider multiwinner elections in Euclidean space using the minimax Chamberlin-Courant rule. In this setting, voters and candidates are embedded in a d-dimensional Euclidean space, and the goal is to choose a committee of k candidates so that the rank of any voter's most preferred candidate in the committee is minimized. (The problem is also equivalent to the ordinal version of the classical k-center problem.) We show that the problem is NP-hard in any dimension d >= 2, and also provably hard to approximate. Our main results are three polynomial-time approximation schemes, each of which finds a committee with provably good minimax score. In all cases, we show that our approximation bounds are tight or close to tight. We mainly focus on the 1-Borda rule but some of our results also hold for the more general r-Borda.

Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirement) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in 1D and 2D, which significantly improve and extend the previous results. Our results include the following: The first data structure for (1 + ∊)-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of O(log3 n/∊), improving the O(nδ/∊) bound of Agarwal et al. [SoCG'20], where δ > 0 denotes an arbitrarily small constant. A data structure for O(1)-approximate dynamic unit-square set cover with amortized update time, substantially improving the O(n1/2+δ) update time of Agarwal et al. [SoCG'20]. A data structure for O(1)-approximate dynamic square set cover with O(n1/2+δ) randomized amortized update time, improving the O(n2/3+δ) update time of Chan and He [SoCG'21]. A data structure for O(1)-approximate dynamic 2D halfplane set cover with O(n17/23+δ) randomized amortized update time. The previous solution for halfplane set cover by Chan and He [SoCG'21] is slower and can only report the size of the approximate solution. The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for (3 + o(1))-approximate dynamic weighted interval set cover with amortized update time and a data structure for O(1)-approximate dynamic weighted unit-square set cover with O(nδ) amortized update time.

We propose an algorithm for the problem of computing shortest paths among curved obstacles in the plane. If the obstacles have $O(n)$ description complexity, then the algorithm runs in $O(n\log n)$ time plus a term dependent on the properties of the boundary arcs. Specifically, if the arcs allow a certain kind of bisector intersection to be computed in constant time, or even in $O(\log n)$ time, then the running time of the overall algorithm is $O(n \log n)$. If the arcs support only constant-time tangent, intersection, and length queries, as is customarily assumed, then the algorithm computes an approximate shortest path, with relative error $\varepsilon$, in time $O(n\log n + n\log \frac{1}{\varepsilon})$. In fact, the algorithm computes an approximate shortest path map, a data structure with $O(n\log n)$ size, that allows it to report the (approximate) length of a shortest path from a fixed source point to any query point in the plane in $O(\log n)$ time. By applying an idea due to Wang [ Proceedings of the $32$nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2021, pp. 810--821], the algorithm's working storage and the size of the approximate shortest path map can be reduced to $O(n)$.

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our article are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in ℝ 1 and ℝ 2 . The first framework uses bootstrapping and gives a (1 + ε)-approximate data structure for dynamic interval set cover in ℝ 1 with O ( n α / ε) amortized update time for any constant α > 0; in ℝ 2 , this method gives O (1)-approximate data structures for unit-square set cover and hitting set with O ( n 1/2+α ) amortized update time. The second framework uses local modification and leads to a (1 + ε)-approximate data structure for dynamic interval hitting set in ℝ 1 with Õ(1/ε) amortized update time; in ℝ 2 , it gives O (1)-approximate data structures for unit-square set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.

In the Multi-Team Formation problem, we are given a ground set C of n candidates, each of which is characterized by a d-dimensional attribute vector in ℝ^d, and two positive integers α and β satisfying α β ≤ n. The goal is to form α disjoint teams T₁,...,T_α ⊆ C, each of which consists of β candidates in C, such that the total score of the teams is maximized, where the score of a team T is the sum of the h_j maximum values of the j-th attributes of the candidates in T, for all j ∈ {1,...,d}. Our main result is an 2^{2^O(d)} n^O(1)-time algorithm for Multi-Team Formation. This bound is ETH-tight since a 2^{2^{d/c}} n^O(1)-time algorithm for any constant c > 12 can be shown to violate the Exponential Time Hypothesis (ETH). Our algorithm runs in polynomial time for all dimensions up to d = clog log n for a sufficiently small constant c > 0. Prior to our work, the existence of a polynomial time algorithm was an open problem even for d = 3.

We consider a multidimensional space partitioning problem, which we call Anonymity-Preserving Partition. Given a set P of n points in ℝ^d and a collection H of m axis-parallel hyperplanes, the hyperplanes of H partition the space into an arrangement A(H) of rectangular cells. Given an integer parameter t > 0, we call a cell C in this arrangement deficient if 0 < |C ∩ P| < t; that is, the cell contains at least one but fewer than t data points of P. Our problem is to remove the minimum number of hyperplanes from H so that there are no deficient cells. We show that the problem is NP-complete for all dimensions d ≥ 2. We present a polynomial-time d-approximation algorithm, for any fixed d, and we also show that the problem can be solved exactly in time (2d-0.924)^k m^O(1) + O(n), where k is the solution size. The one-dimensional case of the problem, where all hyperplanes are parallel, can be solved optimally in polynomial time, but we show that a related Interval Anonymity problem is NP-complete even in one dimension.

Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory (under the names Min-Color Path and Minimum Label Path), wireless sensor networks (Barrier Resilience) and motion planning (Minimum Constraint Removal). It remains NP-hard even for very simple-shaped obstacles such as unit-length line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al., CGTA, 2020]. We also obtain a constant factor approximation for the Minimum Color Prize Collecting Steiner Forest where the goal is to connect multiple request pairs (s1, t1), …, (sk, tk) while minimizing the number of obstacles touched by any (si, ti) path plus a fixed cost of wi for each pair (si, ti) left disconnected. This generalizes the classic Steiner Forest and Prize-Collecting Steiner Forest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for Min-Color Path even on planar graphs since the problem is known to be APX-hard [Eiben and Kanj, TALG, 2020]. Additionally, we show that generalizations of the problem to disconnected obstacles in the plane or connected obstacles in higher dimensions are strongly inapproximable assuming some well-known hardness conjectures.

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in $\mathbb{R}^1$ and $\mathbb{R}^2$. The first framework uses bootstrapping and gives a $(1+\varepsilon)$-approximate data structure for dynamic interval set cover in $\mathbb{R}^1$ with $O(n^α/\varepsilon)$ amortized update time for any constant $α> 0$; in $\mathbb{R}^2$, this method gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set with $O(n^{1/2+α})$ amortized update time. The second framework uses local modification, and leads to a $(1+\varepsilon)$-approximate data structure for dynamic interval hitting set in $\mathbb{R}^1$ with $\widetilde{O}(1/\varepsilon)$ amortized update time; in $\mathbb{R}^2$, it gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set in the \textit{partially} dynamic settings with $\widetilde{O}(1)$ amortized update time.

We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for $$k \le h$$ . Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of $$\varTheta (kn)$$ on the size of this map, and show that it can be computed in $$O(k^2n \log n)$$ time, where n is the total number of obstacle vertices.

Given a set of points P and axis-aligned rectangles R in the plane, a point p in P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k^2) rectangles, we can expose at least Omega(1/k) of the optimal number of points.

Given a set of obstacles and two points, is there a path between the two points that does not cross more than $k$ different obstacles? This is a fundamental problem that has undergone a tremendous amount of work. It is known to be NP-hard, even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). The problem can be generalized into the following graph problem: Given a planar graph $G$ whose vertices are colored by color sets, two designated vertices $s, t \in V(G)$, and $k \in \mathbb{N}$, is there an $s$-$t$ path in $G$ that uses at most $k$ colors? If each obstacle is connected, the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph. We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove that without the color-connectivity property, the problem is W[SAT]-hard parameterized by $k$. A corollary of this result is that, unless W[2] $=$ FPT, the problem cannot be approximated in FPT time to within a factor that is a function of $k$. By describing a generic plane embedding of the graph instances, we show that our hardness results translate to the geometric instances of the problem. We then focus on graphs satisfying the color-connectivity property. By exploiting the planarity of the graph and the connectivity of the colors, we develop topological results to "represent" the valid $s$-$t$ paths containing subsets of colors from any vertex $v$. We employ these results to design an FPT algorithm for the problem parameterized by both $k$ and the treewidth of the graph, and extend this result to obtain an FPT algorithm for the parameterization by both $k$ and the length of the path. The latter result directly implies previous FPT results for various obstacle shapes, such as unit disks and fat regions.

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).

We study the problem of k-dominance in a set of d-dimensional vectors, prove bounds on the number of maxima (skyline vectors), under both worst-case and average-case models, perform experimental evaluation using synthetic and real-world data, and explore an application of k-dominant skyline for extracting a small set of top-ranked vectors in high dimensions where the full skylines can be unmanageably large.

A regret minimizing set Q is a small size representation of a much larger database P so that user queries executed on Q return answers whose scores are not much worse than those on the full dataset. In particular, a k-regret minimizing set has the property that the regret ratio between the score of the top-1 item in Q and the score of the top-k item in P is minimized, where the score of an item is the inner product of the item's attributes with a user's weight (preference) vector. The problem is challenging because we want to find a single representative set Q whose regret ratio is small with respect to all possible user weight vectors. We show that k-regret minimization is NP-Complete for all dimensions d>=3, settling an open problem from Chester et al. [VLDB 2014]. Our main algorithmic contributions are two approximation algorithms, both with provable guarantees, one based on coresets and another based on hitting sets. We perform extensive experimental evaluation of our algorithms, using both real-world and synthetic data, and compare their performance against the solution proposed in [VLDB 14]. The results show that our algorithms are significantly faster and scalable to much larger sets than the greedy algorithm of Chester et al. for comparable quality answers.

We describe an O(n^d) time algorithm for computing the exact probability that two d-dimensional probabilistic point sets are linearly separable, for any fixed d >= 2. A probabilistic point in d-space is the usual point, but with an associated (independent) probability of existence. We also show that the d-dimensional separability problem is equivalent to a (d+1)-dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership by a factor of n [Agarwal et al., ESA, 2014]. In addition, our algorithms can handle "input degeneracies" in which more than k+1 points may lie on a k-dimensional subspace, thus resolving an open problem in [Agarwal et al., ESA, 2014]. Finally, we prove lower bounds for the separability problem via a reduction from the k-SUM problem, which shows in particular that our O(n^2) algorithms for 2-dimensional separability and 3-dimensional convex hull membership are nearly optimal.

The Most Likely Voronoi Diagram is a generalization of the well known Voronoi Diagrams to a stochastic setting, where a stochastic point is a point associated with a given probability of existence, and the cell for such a point is the set of points which would classify the given point as its most likely nearest neighbor. We investigate the complexity of this subdivision of space in d dimensions. We show that in the general case, the complexity of such a subdivision is Omega(n^{2d}) where n is the number of points. This settles an open question raised in a recent (ISAAC 2014) paper of Suri and Verbeek, which first defined the Most Likely Voronoi Diagram. We also show that when the probabilities are assigned using a random permutation of a fixed set of values, in expectation the complexity is only ~O(n^{ceil{d/2}}) where the ~O(*) means that logarithmic factors are suppressed. In the worst case, this bound is tight up to polylog factors.

Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.

Let P be a set of n uncertain points in Red, where each point pi ∈ P is associated with a real value vi and a probability αi ∈ (0,1] of existence, i.e., each pi exists with an independent probability αi. We present algorithms for building an index on P so that for a d-dimensional query rectangle ρ, the expected maximum value or the most-likely maximum value in ρ can be computed quickly. The specific contributions of our paper include the following: (i) The first index of sub-quadratic size to achieve a sub-linear query time in any dimension d ≥ 1. It also provides a trade-off between query time and size of the index. (ii) A conditional lower bound for the most-likely range-max queries, based on the conjectured hardness of the set-intersection problem, which suggests that in the worst case the product (query time)2 x (index size) is Ω((n2}/polylog(n)). (iii) A linear-size index for estimating the expected range-max value within approximation factor 1/2 in O(logc n) time, for some constant c > 0; that is, if the expected maximum value is μ then the query procedure returns a value μ' with μ/2 ≤ μ' ≤ μ. (iv) Extensions of our algorithm to more general uncertainty models and for computing the top-k values of the range-max.

The chromatic art gallery problem asks for the minimum number of "colors" t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility - two points p and q are mutually visible if the smallest axis-aligned rectangle containing them lies within the polygon. Our main result establishes that for a conflict-free guarding of an orthogonal n-gon, in which at least one of the colors seen by every point is unique, the number of colors is Theta(loglog n). By contrast, the best upper bound for orthogonal polygons under standard (non-orthogonal) visibility is O(log n) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is Theta(log n). Finally, our techniques also help us establish the first non-trivial lower bound of Omega(loglog n / logloglog n) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.

We propose an efficient algorithm for discovering the high-level topological structure of a collection of 3-dimensional trajectories. Our algorithm computes a sparse graph representing the latent "bundling" and "unbundling" structure of the trajectory data. Our motivation stems from the emerging area of brain tractography, which aims to construct the connectome of human brain white matter fibers. These fibers can be inferred noninvasively using magnetic resonance imaging (MRI) diffusion scans of the brain interior and modeled abstractly as a set of time-independent geometric trajectories in a three-dimensional brain space. Real neuronal fiber pathways exhibit complex but natural bundling structures, which elude existing MRI reconstruction techniques, but are easily captured by our algorithm. We validate our algorithms both theoretically (uniqueness of the graph representation and provably efficient algorithms) and empirically (using both synthetic and real scanned brain data sets).

We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the jth path, for 1 ≤ j ≤ k, is the shortest path in the free space that is also homotopically distinct from each of the first j – 1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map (k-SPM), in which the homotopy of the kth shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of Θ(k2h + kn) on the worst-case complexity of this map. We also describe an O((k3h + k2n) log (kn)) time algorithm for constructing the map. In fact, the algorithm constructs the jth map for every j ≤ k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O(m log n + k) time and uses O(m + k) space, where m is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O(k2 m(m + kn) log (kn)) time. We invite the reader to play with our applet demonstrating k-SPMs [10].

We consider the problem of embedding an undirected graph into hyperbolic space with minimum distortion. A fundamental problem in its own right, it has also drawn a great deal of interest from applied communities interested in empirical analysis of large-scale graphs. In this paper, we establish a connection between distortion and quasi-cyclicity of graphs, and use it to derive lower and upper bounds on metric distortion. Two particularly simple and natural graphs with large quasi-cyclicity are n-node cycles and n × n square lattices, and our lower bound shows that any hyperbolic-space embedding of these graphs incurs a multiplicative distortion of at least Ω(n/log n). This is in sharp contrast to Euclidean space, where both of these graphs can be embedded with only constant multiplicative distortion. We also establish a relation between quasi-cyclicity and δ-hyperbolicity of a graph as a way to prove upper bounds on the distortion. Using this relation, we show that graphs with small quasi-cyclicity can be embedded into hyperbolic space with only constant additive distortion. Finally, we also present an efficient (linear-time) randomized algorithm for embedding a graph with small quasi-cyclicity into hyperbolic space, so that with high probability at least a (1 − ϵ) fraction of the node-pairs has only constant additive distortion. Our results also give a plausible theoretical explanation for why social networks have been observed to embed well into hyperbolic space: they tend to have small quasi-cyclicity.

We propose an algorithm for the problem of computing shortest paths among curved obstacles in the plane. If the obstacles have O(n) description complexity, then the algorithm runs in O(n log n) time plus a term dependent on the properties of the boundary arcs. Specifically, if the arcs allow a certain kind of bisector intersection to be computed in constant time, or even in O(log n) time, then the running time of the overall algorithm is O(n log n). If the arcs support only constant-time tangent, intersection, and length queries, as is customarily assumed, then the algorithm computes an approximate shortest path, with relative error ε, in time O(n log n + n log 1/ε). In fact, the algorithm computes an approximate shortest path map, a data structure with O(n log n) size, that allows it to report the (approximate) length of a shortest path from a fixed source point to any query point in the plane in O(log n) time.

We investigate the following problem in the visibility-based discrete-time model of pursuit evasion in the plane: how many pursuers are needed to capture an evader in a polygonal environment with obstacles under the minimalist assumption that pursuers and the evader have the same maximum speed? When the environment is a simply-connected (hole-free) polygon of n vertices, we show that Θ (√n) pursuers are both necessary and sufficient in the worst-case. When the environment is a polygon with holes, we prove a lower bound of Ω (n2/3) and an upper bound of O(n5/6) for the number of pursuers that are needed in the worst-case, where n is the total number of vertices including the hole boundaries. More precisely, if the polygon contains h holes, our upper bound is O(n1/2 h1/4), for h ≤ n2/3, and O(n1/3 h1/2) otherwise. These bounds show that capture with minimal assumptions requires significantly more pursuers than what is possible either for visibility detection where pursuers win if one of them can see the evader [Guibas et al. 1999], or for capture when players' movement speed is small compared to "features" of the environment [Klein and Suri, 2012].

Massively parallel DNA sequencing technologies are revolutionizing genomics research. Billions of short reads generated at low costs can be assembled for reconstructing the whole genomes. Unfortunately, the large memory footprint of the existing de novo assembly algorithms makes it challenging to get the assembly done for higher eukaryotes like mammals. In this work, we investigate the memory issue of constructing de Bruijn graph, a core task in leading assembly algorithms, which often consumes several hundreds of gigabytes memory for large genomes. We propose a disk-based partition method, called Minimum Substring Partitioning (MSP), to complete the task using less than 10 gigabytes memory, without runtime slowdown. MSP breaks the short reads into multiple small disjoint partitions so that each partition can be loaded into memory, processed individually and later merged with others to form a de Bruijn graph. By leveraging the overlaps among the k-mers (substring of length k), MSP achieves astonishing compression ratio: The total size of partitions is reduced from Θ(kn) to Θ(n), wherenis the size of the short read database, andkis the length of ak-mer. Experimental results show that our method can build de Bruijn graphs using a commodity computer for any large-volume sequence dataset.

We resolve a several-years old open question in visibility-based pursuit evasion: how many pursuers are needed to capture an evader in an arbitrary polygonal environment with obstacles? The evader is assumed to be adversarial, moves with the same maximum speed as pursuers, and is "sensed'' by a pursuer only when it lies inline-of-sight of that pursuer. The players move in discrete time steps, and the capture occurs when a pursuer reaches the position of the evader on its move. Our main result is that O(√h + log n) pursuers can always win the game with a deterministic search strategy in any polygon with n vertices and h obstacles (holes). In order to achieve this bound, however, we argue that the environment must satisfy a minimum feature size property, which essentially requires the minimum distance between any two vertices to be of the same order as the speed of the players. Without the minimum feature size assumption, we show that Ω < ( √(n/log n)) pursuers are needed in the worst-case even for simply-connected (hole-free) polygons of n vertices! This reveals an unexpected subtlety that seems to have been overlookedin previous work claiming that O(log n) pursuers can always win insimply-connected n-gons. Our lower bound also shows that capturing an evader is inherently more difficult than just "seeing" it because O(log n) pursuers are provably sufficient for line-of-sight detection even against an arbitrarily fast evaderin simple n-gons.

A well-known problem in computational geometry is Klee's measure problem, which asks for the volume of a union of axis-aligned boxes in d-space. In this paper, we consider Klee's measure problem for the special case where a 2-dimensional orthogonal projection of all the boxes has a common corner. We call such a set of boxes 2-grounded and, more generally, a set of boxes is k-grounded if in a k-dimensional orthogonal projection they share a common corner. Our main result is an O(n(d-1)/2log2n) time algorithm for computing Klee's measure for a set of n 2-grounded boxes. This is an improvement of roughly O(√n) compared to the fastest solution of the general problem. The algorithm works for k-grounded boxes, for any k ≥ 2, and in the special case of k=d, also called the hypervolume indicator problem, the time bound can be improved further by a log n factor. The key idea of our technique is to reduce the d-dimensional problem to a semi-dynamic weighted volume problem in dimension d-2. The weighted volume problem requires solving a combinatorial problem of maintaining the sum of ordered products, which may be of independent interest.

We consider a chromatic variant of the art gallery problem, where each guard is assigned one of k distinct colors. A placement of such colored guards is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. What is the smallest number k(n) of colors that ensure a conflict-free covering of all n-vertex polygons? We call this the conflict-free chromatic art gallery problem. The problem is motivated by applications in distributed robotics and wireless sensor networks where colors indicate the wireless frequencies assigned to a set of covering "landmarks" in the environment so that a mobile robot can always communicate with at least one landmark in its line-of-sight range without interference. Our main result shows that k(n) is O(log n) for orthogonal and for monotone polygons, and O(log^2 n) for arbitrary simple polygons. By contrast, if all guards visible from each point must have distinct colors, then k(n)is Omega(n) for arbitrary simple polygons and Omega(sqrt(n)) for orthogonal polygons, as shown by Erickson and LaValle [Proc. of RSS 2011].

Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through the camera network, but need to physically reach the evader to capture it. We allow the evader the knowledge of the current positions of all the pursuers as well---this accords with the standard worst-case analysis model, but also models a practical situation where the evader has ``hacked'' into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment.

We study the complexity of geometric minimum spanning trees under a stochastic model of input: Suppose we are given a master set of points s1,s_2,...,sn in d-dimensional Euclidean space, where each point si is active with some independent and arbitrary but known probability pi. We want to compute the expected length of the minimum spanning tree (MST) of the active points. This particular form of stochastic problems is motivated by the uncertainty inherent in many sources of geometric data but has not been investigated before in computational geometry to the best of our knowledge. Our main results include the following.

We investigate the complexity of shortest paths in time-dependent graphs, in which the costs of edges vary as a function of time, and as a result the shortest path between two nodes s and d can change over time. Our main result is that when the edge cost functions are (polynomial-size) piecewise linear, the shortest path from s to d can change nΘ(log n) times, settling a several-year-old conjecture of Dean [Technical Reports, 1999, 2004]. We also show that the complexity is polynomial if the slopes of the linear function come from a restricted class, present an output-sensitive algorithm for the general case, and describe a scheme for a (1 + ε)-approximation of the travel time function in near-quadratic space. Finally, despite the fact that the arrival time function may have superpolynomial complexity, we show that a minimum delay path for any departure time interval can be computed in polynomial time.

Recent work has shown that, despite the minimal information provided by a binary proximity sensor, a network of these sensors can provide remarkably good target tracking performance. In this article, we examine the performance of such a sensor network for tracking multiple targets. We begin with geometric arguments that address the problem of counting the number of distinct targets, given a snapshot of the sensor readings. We provide necessary and sufficient criteria for an accurate target count in a one-dimensional setting, and provide a greedy algorithm that determines the minimum number of targets that is consistent with the sensor readings. While these combinatorial arguments bring out the difficulty of target counting based on sensor readings at a given time, they leave open the possibility of accurate counting and tracking by exploiting the evolution of the sensor readings over time. To this end, we develop a particle filtering algorithm based on a cost function that penalizes changes in velocity. An extensive set of simulations, as well as experiments with passive infrared sensors, are reported. We conclude that, despite the combinatorial complexity of target counting, probabilistic approaches based on fairly generic models of trajectories yield respectable tracking performance.

Monitoring the performance of large shared computing systems such as the cloud computing infrastructure raises many challenging algorithmic problems. One common problem is to track users with the largest deviation from the norm (outliers), for some measure of performance. Taking a stream-computing perspective, we can think of each user's performance profile as a stream of numbers (such as response times), and the aggregate performance profile of the shared infrastructure as a “braid” of these intermixed streams. The monitoring system's goal then is to untangle this braid sufficiently to track the top k outliers. This paper investigates the space complexity of one-pass algorithms for approximating outliers of this kind, proves lower bounds using multi-party communication complexity, and proposes small-memory heuristic algorithms. On one hand, stream outliers are easily tracked for simple measures, such as max or min, but our theoretical results rule out even good approximations for most of the natural measures such as average, median, or the quantiles. On the other hand, we show through simulation that our proposed heuristics perform quite well for a variety of synthetic data.

In this paper, we present an abstract framework for online approximation of time-series data that yields a unified set of algorithms for several popular models: data streams, amnesic approximation, and out-of-order stream approximation. Our framework essentially develops a popular greedy method of bucket-merging into a more generic form, for which we can prove space-quality approximation bounds. When specialized to piecewise linear bucket approximations and commonly used error metrics, such as L2or L¿, our framework leads to provable error bounds where none were known before, offers new results, or yields simpler and unified algorithms. The conceptual simplicity of our scheme translates into highly practical implementations, as borne out in our simulation studies: the algorithms produce near-optimal approximations, require very small memory footprints, and run extremely fast.

We consider the problem of collectively approximating a set of sensor signals using the least amount of space so that any individual signal can be efficiently reconstructed within a given maximum (L∞) error ε. The problem arises naturally in applications that need to collect large amounts of data from multiple concurrent sources, such as sensors, servers and network routers, and archive them over a long period of time for offline data mining. We present GAMPS, a general framework that addresses this problem by combining several novel techniques. First, it dynamically groups multiple signals together so that signals within each group are correlated and can be maximally compressed jointly. Second, it appropriately scales the amplitudes of different signals within a group and compresses them within the maximum allowed reconstruction error bound. Our schemes are polynomial time O(α, β approximation schemes, meaning that the maximum (L∞) error is at most α ε and it uses at most β times the optimal memory. Finally, GAMPS maintains an index so that various queries can be issued directly on compressed data. Our experiments on several real-world sensor datasets show that GAMPS significantly reduces space without compromising the quality of search and query.

We propose a scalably efficient scheme for detecting large-scale physically correlated events in sensor networks. Specifically, we show that in a network of n sensors arbitrarily distributed in the plane, a sample of O (1/ϵ log 1/ϵ) sensor nodes ( mice ) is sufficient to catch any, and only those , events that affect Ω (ϵ n ) nodes ( elephants ), for any 0 < ϵ < 1, as long as the geometry of the event has a bounded Vapnik-Chervonenkis (VC) dimension. In fact, the scheme is provably able to estimate the size of an event within the approximation error of ±ϵ n /4, which can be improved further at the expense of more mice. The detection algorithm itself requires knowledge of the event geometry (e.g., circle, ellipse, or rectangle) for the sake of computational efficiency, but the combinatorial bound on the sample size (set of mice) depends only on the VC, dimension of the event class and not the precise shape geometry. While nearly optimal in theory, due to implicit constant factors, these “scale-free” bounds still prove too large in practice if applied blindly. We therefore propose heuristic improvements and perform empirical parameter tuning to counter the pessimism inherent in these theoretical estimates. Using a variety of data distributions and event geometries, we show through simulations that the final scheme is eminently scalable and practical, say, for n ≥ 1000. The overall simplicity and generality of our technique suggests that it is well suited for a wide class of sensornet applications, including monitoring of physical environments, network anomalies, network security, or any abstract binary event that affects a significant number of nodes in the network.

We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits while providing minimal descriptions of the estimated target trajectory. Using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution in localizing a target's trajectory is of the order of 1/ρ R , where R is the sensing radius and ρ is the sensor density per unit area. We provide a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a “lowpass” approximation of the trajectory is attainable, and explore the implications of this observation for estimating the target's velocity. We also consider nonideal sensing, employing particle filters to average over noisy sensor observations, and geometric geometric postprocessing of the particle filter output to provide an economical piecewise linear description of the trajectory. In addition to simulation results validating our approaches for both idealized and nonideal sensing, we report on lab-scale experiments using motes with acoustic sensors.

Market-driven dynamic spectrum auctions can drastically improve the spectrum availability for wireless networks struggling to obtain additional spectrum. However, they face significant challenges due to the fear of market manipulation. A truthful or strategy-proof spectrum auction eliminates the fear by enforcing players to bid their true valuations of the spectrum. Hence bidders can avoid the expensive overhead of strategizing over others and the auctioneer can maximize its revenue by assigning spectrum to bidders who value it the most. Conventional truthful designs, however, either fail or become computationally intractable when applied to spectrum auctions. In this paper, we propose VERITAS, a truthful and computationally-efficient spectrum auction to support an eBay-like dynamic spectrum market. VERITAS makes an important contribution of maintaining truthfulness while maximizing spectrum utilization. We show analytically that VERITAS is truthful, efficient, and has a polynomial complexity of O(n3k) when n bidders compete for k spectrum bands. Simulation results show that VERITAS outperforms the extensions of conventional truthful designs by up to 200% in spectrum utilization. Finally, VERITAS supports diverse bidding formats and enables the auctioneer to reconfigure allocations for multiple market objectives.

Modern computer systems are called on to deal with billions of events every second, whether they are executed instructions, accessed memory locations, or forwarded packets. This presents a serious challenge to those who seek to quantify, analyze, or optimize such systems, because important trends and behaviors may easily be lost in a sea of data. We present range-adaptive profiling (RAP) as a new and general-purpose profiling method capable of hierarchically efficiently classifying streams of data in hardware. Through the use of RAP, events in an input stream are dynamically classified into increasingly precise categories, based on the frequency with which they occur. The more important a class, or range of events, the more precisely it is quantified. Despite the dynamic nature of our technique, we build upon tight theoretic bounds covering both worst-case error, as well as the required memory. In the limit, it is known that error and the memory bounds can be independent of the stream size and grow only linearly with the level of precision desired. Significantly, we expose the critical constants in these algorithms and through careful engineering, algorithm redesign, and use of heuristics, we show how a high-performance profile system can be implemented for range-adaptive profiling. RAP can be used on various profiles, such as PCs, load values, and memory addresses, and has a broad range of uses, from hot-region profiling to quantifying cache miss value locality. We propose two methods of implementation of RAP, one in software and the other with specialized hardware, for which we also describe our prototype FPGA implementation. We show that with just 8KB of memory, range profiles can be gathered with an average accuracy of 98%.

We propose a low-overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An ε- cut , for any 0 < ε < 1, is a linear separation of ε n nodes in S from a distinguished node, the base station . Our main result is that, by monitoring the status of just O (1/ε) nodes in the network, the base station can detect whenever an ε- cut occurs. Furthermore, this detection comes with a deterministic guarantee that every reported cut has size at least ε n /2. Besides this combinatorial result, we also propose efficient algorithms for finding the O (1/ε) nodes that should act as sentinels , and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on random sampling.

We propose new algorithms for constructing maximum error (L∞) histograms in the data stream model. Our first algorithm (Min-Merge) achieves the following performance guarantee: using O(B) memory, it constructs a 2B-bucket histogram whose approximation error is at most the error of the optimal B-bucket histogram. Our second algorithm (Min-Increment) achieves a (1 + ε)-approximation of a B-bucket histogram using O(ε-1B log U) space, where U is the size of the domain for data values. The memory requirements of these algorithms are a significant improvement over the previous best schemes for constructing near-optimal histograms in the data stream model, making them ideal for data summary applications where memory is at a premium, such as wireless sensor networks. Our Min-Increment algorithm also extends to the sliding window model without any asymptotic increase in space. Finally, using synthetic and real-world data, we show that our algorithms are indeed as space-efficient in practice as their theoretical analysis predicts - compared to previous best algorithms, they require two or more orders of magnitude less memory for the same approximation error.

We consider the problem of approximating a family of isocontours in a sensor fleld with a topologically-equivalent family of simple polygons. Our algorithm is simple and distributed, it gracefully adapts to any user-specified representation size k, and it delivers a worst-case guarantee for the quality of approximation. In particular, we prove that the topology-respecting Hausdorff error in our k -vertex approximation is within a small constant factor of the optimal error possible with Θ(k/log m) vertices, where m is the number of contours. Evaluation of the algorithm on real data suggests that the size increase factor in practice is a constant near 2 .6, and shows no error increase. Our simulation results using a variety of synthetic and real data show that the algorithm smoothly handles complex isocontours, even for representation sizes as small as 32 or 48. Because isocontours are widely used to represent and communicate bi-variate signals, our technique is broadly applicable to innetwork aggregation and summarization of spatial data in sensor networks.

Recent work has shown that, despite the minimal information provided by a binary proximity sensor, a network of such sensors can provide remarkably good target tracking performance. In this paper, we examine the performance of such a sensor network for tracking multiple targets. We begin with geometric arguments that address the problem of counting the number of distinct targets, given a snapshot of the sensor readings. We provide necessary and sufficient criteria for an accurate target count in a one-dimensional setting, and provide a greedy algorithm that determines the minimum number of targets that is consistent with the sensor readings. While these combinatorial arguments bring out the difficulty of target counting based on sensor readings at a given time, they leave open the possibility of accurate counting and tracking by exploiting the evolution of the sensor readings across time. To this end, we develop a particle filtering algorithm based on a cost function that penalizes changes in velocity. An extensive set of simulations, as well as experiments with passive infrared sensors, are reported. We conclude that, despite the combinatorial complexity of target counting, probabilistic approaches based on fairly generic models for the trajectories yield respectable tracking performance.

We propose a scalably efficient scheme for detecting large-scale physically-correlated events in sensor networks. Specifically, we show that in a network of n sensors arbitrarily distributed in the plane, a sample of O(1/ε log 1/ε) sensor nodes (mice) is sufficient to catch any, and only those, events that affect Ω(εn) nodes (elephants), for any 0 < ε < 1, as long as the geometry of the event has a bounded Vapnik-Chervonenkis (VC) dimension. In fact, the scheme is provably able to estimate the size of an event within the approximation error of ±εn/4, which can be improved further at the expense of more mice. The detection algorithm itself requires knowledge of the event geometry (e.g. circle, ellipse, or rectangle) for the sake of computational efficiency, but the combinatorial bound on the sample size (set of mice) depends only on the VC dimension of the event class and not the precise shape geometry.

We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed by Hershberger and Suri [2001], and can yield a factor Θ( n ) improvement for this problem. But there is a caveat: The fast replacement paths subroutine is known to fail for some directed graphs. However, the failure is easily detected, and so our k shortest paths algorithm optimistically uses the fast subroutine, then switches to a slower but correct algorithm if a failure is detected. Thus, the algorithm achieves its Θ( n ) speed advantage only when the optimism is justified. Our empirical results show that the replacement paths failure is a rare phenomenon, and the new algorithm outperforms the current best algorithms; the improvement can be substantial in large graphs. For instance, on GIS map data with about 5,000 nodes and 12,000 edges, our algorithm is 4--8 times faster. In synthetic graphs modeling wireless ad hoc networks, our algorithm is about 20 times faster.

We prove superlinear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem: Given a directed graph G with non-negative edge weights, and a shortest path P = {e1, e2, …, ep} between two nodes s and t, compute the shortest path distances from s to t in each of the p graphs obtained from G by deleting one of the edges ei. We show that the replacement paths problem requires Ω(m √n) time in the worst case whenever m = O(n √n). Our construction also implies a similar lower bound on the k shortest simple paths problem for a broad class of algorithms that includes all known algorithms for the problem. To put our lower bound in perspective, we note that both these problems (replacement paths and k shortest simple paths) can be solved in near-linear time for undirected graphs.

We consider the following problem: given an on-line, possibly unbounded stream of two-dimensional points, how can we summarize its spatial distribution or shape using a small, bounded amount of memory? We propose a novel scheme, called ClusterHull, which represents the shape of the stream as a dynamic collection of convex hulls, with a total of at most m vertices, where m is the size of the memory. The algorithm dynamically adjusts both the number of hulls and the number of vertices in each hull to best represent the stream using its fixed memory budget. This algorithm addresses a problem whose importance is increasingly recognized, namely the problem of summarizing real-time data streams to enable on-line analytical processing. As a motivating example, consider habitat monitoring using wireless sensor networks. The sensors produce a steady stream of geographic data, namely, the locations of objects being tracked. In order to conserve their limited resources (power, bandwidth, storage), the sensors can compute, store, and exchange ClusterHull summaries of their data, without losing important geometric information. We are not aware of other schemes specifically designed for capturing shape information in geometric data streams, and so we compare ClusterHull with some of the best general-purpose clustering schemes such as CURE, k-median, and LSEARCH. We show through experiments that ClusterHull is able to represent the shape of two-dimensional data streams more faithfully and flexibly than the stream versions of these clustering algorithms.

Modern computer systems are called on to deal with billions of events every second, whether they are instructions executed, memory locations accessed, or packets forwarded. This presents a serious challenge to those who seek to quantify, analyze, or optimize such systems, because important trends and behaviors may easily be lost in a sea of data. We present range adaptive profiling (RAP) as a new and general purpose profiling method capable of hierarchically classifying streams of data efficiently in hardware. Through the use of RAP, events in an input stream are dynamically classified into increasingly precise categories based on the frequency with which they occur. The more important a class, or range of events, the more precisely it is quantified. Despite the dynamic nature of our technique, we build upon tight theoretic bounds covering both worst-case error as well as the required memory. In the limit, it is known that error and the memory bounds can be independent of the stream size, and grow only linearly with the level of precision desired. Significantly, we expose the critical constants in these algorithms and through careful engineering, algorithm re-design, and use of heuristics, we show how a high performance profile system can be implemented for range adaptive profiling. RAP can be used on various profiles such as PCs, load values, and memory addresses, and has a broad range of uses, from hot-region profiling to quantifying cache miss value locality. We propose two methods of implementation, one in software and the other with specialized hardware, and we show that with just 8k bytes of memory range profiles can be gathered with an average accuracy of 98%.

Recently there has been a growing interest in detecting patterns and analyzing trends in data that are generated continuously, often delivered in some fixed order and at a rapid rate, in the form of a data stream [5, 6]. When the stream consists of spatial data, its geometric "shape" can convey important qualitative aspects of the data set more effectively than many numerical statistics. In a stream setting, where the data must be constantly discarded and compressed, special care must be taken to ensure that the compressed summary faithfully captures the overall shape of the point distribution. We propose a novel scheme, ClusterHulls, to represent the shape of a stream of two-dimensional points. Our scheme is particularly useful when the input contains clusters with widely varying shapes and sizes, and the boundary shape, orientation, or volume of those clusters may be important in the analysis.

Abstract — We propose efficient distributed algorithms to aid navigation of a user through a geographic area covered by sensors. The sensors sense the level of danger at their locations and we use this information to find a safe path for the user through the sensor field. Traditional distributed navigation algorithms rely upon flooding the whole network with packets to find an optimal safe path. To reduce the communication expense, we introduce the concept of a skeleton graph which is a sparse subset of the true sensor network communication graph. Using skeleton graphs we show that it is possible to find approximate safe paths with much lower communication cost. We give tight theoretical guarantees on the quality of our approximation and by simulation, show the effectiveness of our algorithms in realistic sensor network situations. I.

Typical wireless routing protocols like AODV/DSR are not scalable to very large networks because they employ flooding for route discovery. Geographic routing protocols like GPSR are highly scalable because they require minimum control overhead, but depend on idealized link quality models (such as the unit disk model) which are not always applicable. We explore the routing spectrum between these two extremes under a realistic random link quality model. It is common wisdom that by adding limited flooding to a protocol like geographic routing improves quality. In this paper, we provide a formal and quantitative formulation of this trade-off, and show both analytically and experimentally that a significant improvement in path quality is possible by searching a narrow region around the geographic straight-line path between the source and destination. In particular, if the end-to-end throughput is measured as the product of link reliabilities in a path, then we demonstrate that the path quality improves exponentially as the search region is broadened

We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits. In particular, using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution Δ in localizing a target's trajectory is of the order of 1overρ R, where R is the sensing radius and ρ is the sensor density per unit area. Using an Occam's razor approach, we then design a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a "lowpass" approximation of the trajectory is attainable, and explore the implications of this obervation for estimating the target's velocity.We show through simulation the effectiveness of the geometric algorithm in tracking both the trajectory and the velocity of the target for idealized models. For non-ideal sensors exhibiting sensing errors, the geometric algorithm can yield poor performance. We show that non-idealities can be handled well using a particle filter based approach, and that geometric post-processing of the output of the Particle Filter algorithm yields an economical path description as in the idealized setting. Finally, we report on our lab-scale experiments using motes with acoustic sensors to validate our theoretical and simulation results.

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensor network databases like TinyDB [S. Madden et al., 2002] are the dominant architectures to extract and manage data in such networks. Since sensors have significant power constraints (battery life), and high communication costs, design of energy efficient communication algorithms is of great importance. The data flow in a sensor database is very different from data flow in an ordinary network and poses novel challenges in designing efficient routing algorithms. In this work we explore the problem of energy efficient routing for various different types of database queries and show that in general, this problem is NP-complete. We give a constant factor approximation algorithm for one class of query, and for other queries give heuristic algorithms. We evaluate the efficiency of the proposed algorithms by simulation and demonstrate their near optimal performance for various network sizes.

We propose a low overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An /spl epsiv/-cut, for any 0</spl epsiv/<1, is a linear separation of /spl epsiv/n nodes in S from a distinguished node, the base station. We show that the base station can detect whenever an /spl epsiv/-cut occurs by monitoring the status of just O(1//spl epsiv/) nodes in the network. Our scheme is deterministic and it is free of false positives: no reported cut has size smaller than 1/2/spl epsiv/n. Besides this combinatorial result, we also propose efficient algorithms for finding the O(1//spl epsiv/) nodes that should act as sentinels, and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on sampling.

Heavy hitters, which are items occurring with frequency above a given threshold, are an important aggregation and summary tool when processing data streams or data warehouses. Hierarchical heavy hitters (HHHs) have been introduced as a natural generalization for hierarchical data domains, including multi-dimensional data. An item x in a hierarchy is called a ϕ-HHH if its frequency after discounting the frequencies of all its descendant hierarchical heavy hitters exceeds ϕn, where ϕ is a user-specified parameter and n is the size of the data set. Recently, single-pass schemes have been proposed for computing ϕ-HHHs using space roughly O(1/ϕ log(ϕn)). The frequency estimates of these algorithms, however, hold only for the total frequencies of items, and not the discounted frequencies; this leads to false positives because the discounted frequency can be significantly smaller than the total frequency. This paper attempts to explain the difficulty of finding hierarchical heavy hitters with better accuracy. We show that a single-pass deterministic scheme that computes ϕ-HHHs in a d-dimensional hierarchy with any approximation guarantee must use Ω(1/ϕd+1) space. This bound is tight: in fact, we present a data stream algorithm that can report the ϕ-HHHs without false positives in O(1/ϕd+1) space.

Simulation environments are an important tool for the evaluation of new concepts in networking. The study of mobile ad hoc networks depends on understanding protocols from simulations, before these protocols are implemented in a real-world setting. To produce a real-world environment within which an ad hoc network can be formed among a set of nodes, there is a need for the development of realistic, generic and comprehensive mobility, and signal propagation models. In this paper, we propose the design of a mobility and signal propagation model that can be used in simulations to produce realistic network scenarios. Our model allows the placement of obstacles that restrict movement and signal propagation. Movement paths are constructed as Voronoi tessellations with the corner points of these obstacles as Voronoi sites. Our mobility model also introduces a signal propagation model that emulates properties of fading in the presence of obstacles. As a result, we have developed a complete environment in which network protocols can be studied on the basis of numerous performance metrics. Through simulation, we show that the proposed mobility model has a significant impact on network performance, especially when compared with other mobility models. In addition, we also observe that the performance of ad hoc network protocols is effected when different mobility scenarios are utilized.

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space-filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined into a BSP of size $O(n^{(d+1)/{3}})$ for all $d \geq 3$ and that such a partition can be computed in time ${O(K\log n)}$, where K is the size of the BSP produced. Our upper bound on the BSP size is tight for 3-dimensional subdivisions; in higher dimensions, this is the first nontrivial result for general full-dimensional boxes. We also present a lower bound construction for a subdivision of n boxes in d-space for which every axis-aligned BSP has $\Omega(n^{\beta(d)})$ size, where $\beta(d)$ converges to $(1+\sqrt{5})/2$ as $d \rightarrow \infty$.

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined into a BSP of size O(n d+1/3), for all d ≥ 3, and that such a partition can be computed in time O(K log n), where K is the size of the BSP produced. Our upper bound on the BSP size is tight for 3-dimensional subdivisions in higher dimensions, this is the first nontrivial result for general full-dimensional boxes. We also present a lower bound construction for a subdivision of n boxes in d-space that requires a BSP of size Ω(n946;(d)), where β(d) converges to (1+ √5 )/2 as d → ∞.

We consider the problem of approximate range counting over streams of d-dimensional points. In the data stream model, the algorithm makes a single scan of the data, which is presented in an arbitrary order, and computes a compact summary (called a sketch). The sketch, whose size depends on the approximation parameter ε, can be used to count the number of points inside a query range within additive error εn, where n is the size of the stream. We present several results, deterministic and randomized, for both rectangle and halfplane ranges.

Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations, scientific measurements of earth or atmospheric phenomena, etc. How can one summarize such data streams using limited storage so that many natural geometric queries can be answered faithfully? Some examples of such queries are: report the smallest convex region in which a chemical leak has been sensed, or track the diameter of the dataset. One can also pose queries over multiple streams: track the minimum distance between the convex hulls of two data streams; or report when datasets A and B are no longer linearly separable.In this paper, we propose an adaptive sampling scheme that gives provably optimal error bounds for extremal problems of this nature. All our results follow from a single technique for computing the approximate convex hull of a point stream in a single pass. Our main result is this: given a stream of two-dimensional points and an integer r, we can maintain an adaptive sample of at most 2r + 1 points such that the distance between the true convex hull and the convex hull of the sample points is O(D/r2), where D is the diameter of the sample set. With our sample convex hull, all the queries mentioned above can be answered in either O(log r) or O(r) time.

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very expensive. Another important issue in the context of sensor-based information systems is that individual sensor readings are inherently unreliable. In order to address these two aspects, sensor database systems like TinyDB and Cougar enable in-network data aggregation to reduce the communication cost and improve reliability. The existing data aggregation techniques, however, are limited to relatively simple types of queries such as SUM, COUNT, AVG, and MIN/MAX. In this paper we propose a data aggregation scheme that significantly extends the class of queries that can be answered using sensor networks. These queries include (approximate) quantiles, such as the median, the most frequent data values, such as the consensus value, a histogram of the data distribution, as well as range queries. In our scheme, each sensor aggregates the data it has received from other sensors into a fixed (user specified) size message. We provide strict theoretical guarantees on the approximation quality of the queries in terms of the message size. We evaluate the performance of our aggregation scheme by simulation and demonstrate its accuracy, scalability and low resource utilization for highly variable input data sets.

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with or, more generally, as the pth power of the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared to the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to 1 + 2/√3 ≈ 2.15. We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.

One of the most important methods for evaluating the characteristics of ad hoc networking protocols is through the use of simulation. Simulation provides researchers with a number of significant benefits, including repeatable scenarios, isolation of parameters, and exploration of a variety of metrics. The topology and movement of the nodes in the simulation are key factors in the performance of the network protocol under study. Once the nodes have been initially distributed, the mobility model dictates the movement of the nodes within the network. Because the mobility of the nodes directly impacts the performance of the protocols, simulation results obtained with unrealistic movement models may not correctly reflect the true performance of the protocols. The majority of existing mobility models for ad hoc networks do not provide realistic movement scenarios; they are limited to random walk models without any obstacles. In this paper, we propose to create more realistic movement models through the incorporation of obstacles. These obstacles are utilized to both restrict node movement as well as wireless transmissions. In addition to the inclusion of obstacles, we construct movement paths using the Voronoi diagram of obstacle vertices. Nodes can then be randomly distributed across the paths, and can use shortest path route computations to destinations at randomly chosen obstacles. Simulation results show that the use of obstacles and pathways has a significant impact on the performance of ad hoc network protocols.

Peer-to-peer (P2P) networks are self-organizing, distributed systems, with no centralized authority or infrastructure. Because of the voluntary participation, the availability of resources in a P2P system can be highly variable and unpredictable. We use ideas from game theory to study the interaction of strategic and rational peers, and propose a differential service-based incentive scheme to improve the system's performance.

Peer-to-peer computing paradigm is emerging as a scalable and robust model for sharing media objects. We propose an architecture and describe the associated algorithms and data structures to support the execution of range selection queries over data scattered across a P2P network especially for resource discovery in grid environments. We develop a distributed data structure referred to as a range addressable network that provides the following two quality-of-service guarantees: (i) the located peer is one with the smallest superset of the query range (important from the application perspective), and (ii) in a P2P network of n peers, a query is routed through O(log n) peers before the intended peer is found (important from the system perspective). Our preliminary experimental evaluation indicates that the range addressable network has desirable properties of scalability and load-balancing, which are crucial for the success of a large-scale P2P system.

We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multi-unit allocation problem. The bidding language in our auctions allows marginal-decreasing piecewise constant curves. First, we develop a fully polynomial-time approximation scheme for the multi-unit allocation problem, which computes a (1+ε)≈ in worst-case time T = O(n3/ε), given n bids each with a constant number of pieces. Second, we embed this approximation scheme within a Vickrey-Clarke-Groves (VCG) mechanism and compute payments to n agents for an asymptotic cost of O(T log n). The maximal possible gain from manipulation to a bidder in the combined scheme is bounded by ε/(1+ε) V, where V is the total surplus in the efficient outcome.

No abstract available.

A naive algorithm for the replacement paths problem runs in O(n(m+n logn)) time, executing the single-source shortest path algorithm up to n times. In our paper [3], we claimed that the replacement paths problem can be solved inO(m+n logn) time for both undirected and directed graphs. However, there is a flaw that invalidates the algorithm for directed graphs. (The algorithm for undirected graphs remains valid.) The same bound for undirected graphs is also achieved by Nardelli, Proietti, and Widmayer [6], who solve the most vital node problem with an algorithm that also solves the replacement paths problem. Their work is in turn based on earlier work by Malik, Mittal and Gupta [5], Ball, Golden, and Vohra [1] and BarNoy, Khuller, and Schieber [2]. The error in our algorithm for directed graphs led us to investigate the hardness of the replacement paths problem and other related problems. We have recently established lower bounds that show that no replacement paths algorithm of a certain class (including all known algorithms) can achieve the running time of the algorithm for undirected graphs [4]. The mistake in the directed graph algorithm of [3] occurs on page 257, just after Lemma 2, where we say “A simple corollary of this lemma is the fact that if (u; v) is the single edge of path(x; y; G n e) in E(Vx; Vy), then

In the current Internet, Web content is increasingly being cached closer to the end user to reduce network and Web server load and improve performance. Existing Web caching systems typically cache entire Web documents and attempt to keep them consistent with the origin server. This approach works well for text and images; for bandwidth intensive multimedia data such as audio and video, caching entire documents is not cost effective and does not scale. An alternative approach is to cache parts of the multimedia stream on different caches in the network and coordinate stream playback from these independent caches. From the perspective of the clients, the collection of cooperating distributed caches acts as a single fault tolerant, scalable cache. In this paper, we focus on data placement and replacement techniques for such co-operating distributed caches. Specifically, we propose the following new schemes that work together. 1) A family of distributed layouts, consisting of two layouts, namely RCache and Silo. The RCache layout is a simple, randomized, easy-to-implement layout that distributes constant length segments of a clip among caches and provides modest storage efficiency. The Silo scheme improves upon RCache; it accounts for long term clip popularity and intraclip segment popularity metrics and provides parameters to tune storage efficiency, server load, and playback switch-overs. 2) Rainbow, a local data replacement scheme based on the concept of segment access potential that accurately captures the popularity metrics. 3) Caching Token, a dynamic global data replacement or redistribution scheme that exploits existing data in distributed caches to minimize data distribution overhead. Our schemes optimize storage space, startup latency, server load, network bandwidth usage, and overhead from playback switch-overs. Our analytical and simulation results show that the silo scheme provides three to eight times higher cache hit ratio than a comparable traditional Web caching system that has the same amount of storage space.

Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let $\poly$ be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside $\poly$. (A configuration specifies both a location and a direction of travel.) We present an O(n 2 log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.

We develop a combinatorial algorithm for determining a minimum volume simplex enclosing a set of points in ${\cal R}^3$. If the convex hull of the points has n vertices, then our algorithm takes $\Theta(n^4)$ time. Combining our exact but slow algorithm with a simple but crude approximation technique, we also develop an $\varepsilon$-approximation algorithm. The algorithm computes in $O(n + 1/\varepsilon^6)$ time a simplex whose volume is within $(1 + \varepsilon)$ factor of the optimal for any $\varepsilon > 0$.

We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized entity, such as the Internet, in which multiple self-interested agents own different parts of the network, then auction-based pricing seems appropriate. A celebrated result from auction theory shows that the use of Vickrey pricing motivates the owners of the network resources to bid truthfully. In Vickrey's scheme, each agent is compensated in proportion to the marginal utility he brings to the auction. In the context of shortest path routing, an edge's utility is the value by which it lowers the length of the shortest path, i.e., the difference between the shortest path lengths with and without the edge. Our problem is to compute these marginal values for all the edges of the network efficiently. The naive method requires solving the single-source shortest path problem up to n times, for an n-node network. We show that the Vickrey prices for all the edges can be computed in the same asymptotic time complexity as one single-source shortest path problem. This solves an open problem posed by N. Nisan and A. Ronen (1999).

In this paper, we introduce a new IP lookup scheme with worst-case search and update time of O(log n), where n is the number of prefixes in the forwarding table. Our scheme is based on a new data structure, a multiway range tree. While existing lookup schemes are good for IPv4, they do not scale well in both lookup speed and update costs when addresses grow longer as in the IPv6 proposal. Thus our lookup scheme is the first lookup scheme to offer fast lookups and updates for IPv6 while remaining competitive for IPv4.

Label switched networks have become increasingly attractive to both network providers and customers. By creating aggregate, bandwidth-reserved flows, these networks offer routing flexibility, predictable bandwidth usage, and quality-of-service (QoS) provisioning. This flexibility in routing enables fault-persistent QoS reservations, where connectivity, and allotted bandwidth remains available, even if some links or network nodes fail. The automatic switch-over from a now-defunct path to a new, working path is known as restoration. Restoring bandwidth-guaranteed paths requires allocation of resources on backup paths that will be used in the event of faults. In this paper, we investigate distributed algorithms for routing with backup restoration. Specifically, we propose a new concept of backup load distribution matrix that captures partial network state, greatly reducing the amount of routing information maintained and transmitted while achieving efficient bandwidth usage. We present and simulate two new distributed routing algorithms, which provide significant improvements in rejection rates and provide substantial savings in bandwidth used and call setup time compared to existing algorithms.

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and diffserv. Classification can be based on an arbitrary number of fields in the packet header. Performing classification quickly on an arbitrary number of fields is known to be difficult, and has poor worst-case complexity. In this paper, we re-examine two basic mechanisms that have been dismissed in the literature as being too inefficient: backtracking search and set pruning tries. We find using real databases that the time for backtracking search is much better than the worst-case bound; instead of /spl Omega/((logN)/sup k-1/), the search time is only roughly twice the optimal search time. Similarly, we find that set pruning tries (using a DAG optimization) have much better storage costs than the worst-case bound. We also propose several new techniques to further improve the two basic mechanisms. Our major ideas are: (i) backtracking search on a small memory budget, (ii) a novel compression algorithm, (iii) pipelining the search, (iv) the ability to trade-off smoothly between backtracking and set pruning. We quantify the performance gain of each technique using real databases. We show that on real firewall databases our schemes, with the accompanying optimizations, are close to optimal in time and storage.

With the rapidly growing importance of multicast in the Internet there have been a proposal, the RFC 2627, for scalable key distribution such that when the nth user joins or leaves a group, broadcasting /spl Theta/(logn) encrypted messages is sufficient to redistribute the keys. We show that this bound is also necessary for a general class of key distribution schemes and under different assumptions on user capabilities. While key distribution schemes can trade addition cost for deletion cost, for any scheme there is a sequence of 2n insertion and deletions whose total cost is /spl Omega/(nlogn). Thus, any key distribution scheme has a worst-case cost of /spl Omega/(logn) either for adding or for deleting a user.

Routers can use packet classification to support advanced functions. Routers with packet classification capability can forward packets based on multiple header fields, such as source address, protocol type, or application port numbers. The destination-based forwarding can be thought of as one-dimensional packet classification. While several efficient solutions are known for the one-dimensional IP lookup problem, the multi-dimensional packet classification has proved to be far more difficult. While an O(log w) time scheme is known for the IP lookup, Srinivisan et al. (1999) show a lower bound of /spl Omega/(/spl omega//sup k-1/) for k-dimensional filter lookup, where /spl omega/ is the number of bits in a header field. In particular, this lower bound precludes the possibility of a binary search like scheme even for 2-dimensional filters. In this paper, we examine this lower bound more closely, and discover that the lower bound depends crucially on conflicts in the filter database. We then show that for two-dimensional conflict-free filters, a binary search scheme does work! Our lookup scheme requires O(log/sup 2/ /spl omega/) hashes in the worst-case, and uses O(n log/sup 2/ /spl omega/) memory. Alternatively, our algorithm can be viewed as making O (log /spl omega/) calls to a prefix lookup scheme. It has been observed in practice that filter databases have very few conflicts, and these conflicts can be removed by adding additional filters (one per conflict). Thus, our scheme may also be quite practical. Our simulation and experimental results show that the proposed scheme also performs as good as or better than existing schemes.

We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. While the disks move continuously, their connectivity changes at discrete times. Our main result is an O(n) space data structure that takes O(log n/ log log n) time per connectivity query of the form "are disks A and B in the same connected component?" A straightforward approach based on dynamically maintaining the overlap graph requires## n 2 ) space. Our data structure requires only linear space and must deal with O(n 2+# ) updates in the worst case, each requiring O(log 2 n) amortized time. This number of updates is close to optimal, since a set of n moving unit disks can undergo## n 2 ) connectivity changes. 1 Introduction Motivated by applications in mobile ...

Packet filters are rules for classifying packets based on their header fields. Packet classification is essential to routers supporting services such as quality of service (QoS), virtual private networks (VPNs), and firewalls. A filter conflict occurs when two or more filters overlap, creating an ambiguity in packet classification. Current techniques for resolving filter conflicts are based on prioritizing conflicting filters, and choosing the higher priority filter. We show that such ordering does not always work. Instead, we propose a new scheme for conflict resolution, which is based on the idea of adding resolve filters. Our main results are algorithms for detecting and resolving conflicts in a filter database. We have tried our algorithm on 3 existing firewall databases, and have found conflicts, which are potential security holes, in each of them.

We develop a kinetic data structure (KDS) for maintaining the connectivity of a set of axis-aligned rectangles moving in the plane. In the kinetic framework, each rectangle is assumed to travel along a low-degree algebraic path, specified by a flight plan---if the flight plan changes, the data structure is informed about it. The connectivity of rectangles changes only at discrete moments, given by the times when the order of rectangles along either axis changes. Our main result is a kinetic data structure of size O(n log n) that requires O(log 2 n) amortized time for each update, and answers connectivity queries in worst-case time O(log n= log log n). 1 Introduction Connectivity is the most basic of graph properties, with many applications to real-world problems. Applications of connectivity range from electrical connectivity in integrated circuits to network connectivity in communication networks. In this paper, we explore the problem of maintaining the connectivity of n axis-alig...

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and QoS routing. Packet classification requires matching each packet against a database of filters (or rules), and forwarding the packet according to the highest priority filter. Existing filter schemes with fast lookup time do not scale to large filter databases. Other more scalable schemes work for 2-dimensional filters, but their lookup times degrade quickly with each additional dimension. While there exist good hardware solutions, our new schemes are geared towards software implementation.We introduce a generic packet classification algorithm, called Tuple Space Search (TSS). Because real databases typically use only a small number of distinct field lengths, by mapping filters to tuples even a simple linear search of the tuple space can provide significant speedup over naive linear search over the filters. Each tuple is maintained as a hash table that can be searched in one memory access. We then introduce techniques for further refining the search of the tuple space, and demonstrate their effectiveness on some firewall databases. For example, a real database of 278 filters had a tuple space of 41 which our algorithm prunes to 11 tuples. Even as we increased the filter database size from 1K to 100K (using a random two-dimensional filter generation model), the number of tuples grew from 53 to only 186, and the pruned tuples only grew from 1 to 4. Our Pruned Tuple Space search is also the only scheme known to us that allows fast updates and fast search times. We also show a lower bound on the general tuple space search problem, and describe an optimal algorithm, called Rectangle Search, for two-dimensional filters.

Bounding boxes are commonly used in computer graphics and other fields to improve the performance of algorithms that should process only the intersecting objects.A bounding-box-based heuristic avoids unnecessary intersection processing by eliminating the pairs whose bounding boxes are disjoint.Empirical evidence suggests that the heuristic works well in many practical applications, although its worst-case performance can be bad for certain pathological inputs.What is a pathological input, however, is not well understood, and consequently there is no guarantee that the heuristic will always work well in a specific application.In this paper, we analyze the performance of bounding box heuristic in terms of two natural shape parameters, aspect ratio and scale factor.These parameters can be used to realistically measure the degree to which the objects are pathologically shaped.We derive tight worst-case bounds on the performance for bounding box heuristic.One of the significant contributions of our paper is that we only require that objects be well shaped on average.Somewhat surprisingly, the bounds are significantly different from the case when all objects are well shaped.

We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(n log n) and requires O(n log n) space, where n is the total number of vertices in the obstacle polygons. The algorithm is based on an efficient implementation of wavefront propagation among polygonal obstacles, and it actually computes a planar map encoding shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previously published results on the shortest path problem. Finally, we also discuss extensions to more general shortest path problems, involving nonpoint and multiple sources.

Heuristics that exploit bouning boxes are common in algorithms for rendering, modeling, and animation. While experience has shown that bounding boxes improve the performance of these algorithms in practice, the previous theoretical analysis has concluded that bounding boxes perform poorly in the worst case. This paper reconciles this discrepancy by analyzing intersections among n geometric objects in terms of two parameters: α an upper bound on the aspect ratio or elongatedness of each object; and σ an upper bound on the scale factor or size disparity between the largest and smallest objects. Letting K o and K b be the number of intersecting object pairs and bounding box pairs, respectively, we analyze a ratio measure of the bounding boxes' efficiency, ρ = K b / (n + K 0 ) . The analysis proves that ρ = O(α√σlog 2 σ) and ρ = Ω(α√σ) . One important consequence is that if α and σ are small constants (as is often the case in practice), then K b = O ( K o )+ O ( n , so an algorithm that uses bounding boxes has time complexity proportional to the number of actual object intersections. This theoretical result validates the efficiency that bounding boxes have demonstrated in practice. Another consequence of our analysis is a proof of the output-sensitivity of an algorithm for reporting all intersecting pairs in a set of n convex polyhedra with constant α and σ. The algorithm takes time O ( n log d -1 n + K o log d -1 n ) for dimension d = 2, 3. This running time improves on the performance of previous algorithms, which make no assumptions about α and σ.

International audience

In Layer Four switching, the route and resources allocated to a packet are determined by the destination address as well as other header fields of the packet such as source address, TCP and UDP port numbers. Layer Four switching unifies firewall processing, RSVP style resource reservation filters, QoS Routing, and normal unicast and multicast forwarding into a single framework. In this framework, the forwarding database of a router consists of a potentially large number of filters on key header fields. A given packet header can match multiple filters, so each filter is given a cost, and the packet is forwarded using the least cost matching filter.In this paper, we describe two new algorithms for solving the least cost matching filter problem at high speeds. Our first algorithm is based on a grid-of-tries construction and works optimally for processing filters consisting of two prefix fields (such as destination-source filters) using linear space. Our second algorithm, cross-producting, provides fast lookup times for arbitrary filters but potentially requires large storage. We describe a combination scheme that combines the advantages of both schemes. The combination scheme can be optimized to handle pure destination prefix filters in 4 memory accesses, destination-source filters in 8 memory accesses worst case, and all other filters in 11 memory accesses in the typical case.

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ d for fixed d . More specifically, let 𝒯 be any set of s halfspaces. Let x =(x 1 , …, x d ) be an arbitrary point in ℛ d . With each t ∈ 𝒯 we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, 𝒞 d s , that we study consists of all concepts formed by any Boolean function over I t1 , …, I ts for t i ∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ d given that the VC-dimension of 𝒞 has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.

Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: given a set S of n points sampled from a bivariate function f(x,y) and an input parameter $\eps > 0$, compute a piecewise-linear function $\Sigma(x,y)$ of minimum complexity (that is, an xy-monotone polyhedral surface, with a minimum number of vertices, edges, or faces) such that $| \Sigma(x_p, y_p) \; - \; z_p | \:\:\leq\:\: \eps$ for all $(x_p, y_p, z_p) \in S$. We give hardness evidence for this problem, by showing that a closely related problem is NP-hard. The main result of our paper is a polynomial-time approximation algorithm that computes a piecewise-linear surface of size O(K o log K o ), where K o is the complexity of an optimal surface satisfying the constraints of the problem. The technique developed in our paper is more general and applies to several other problems that deal with partitioning of points (or other objects) subject to certain geometric constraints. For instance, we get the same approximation bound for the following problem arising in machine learning: given n "red" and m "blue" points in the plane, find a minimum number of pairwise disjoint triangles such that each blue point is covered by some triangle and no red point lies in any of the triangles.

Article Efficient breakout routing in printed circuit boards Share on Authors: John Hershberger Mentor Graphics, 1001 Ridder Park Drive, San Jose, CA Mentor Graphics, 1001 Ridder Park Drive, San Jose, CAView Profile , Subhash Suri Department of Computer Science, Washington University, St. Louis, MO Department of Computer Science, Washington University, St. Louis, MOView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 460–462https://doi.org/10.1145/262839.263082Online:01 August 1997Publication History 9citation256DownloadsMetricsTotal Citations9Total Downloads256Last 12 Months5Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We describe an efficient fair queuing scheme, leap forward virtual clock, that provides end-to-end delay bounds similar to weighted fair queuing (WFQ), along with throughput fairness. Our scheme can be implemented with a worst-case time O(loglogN) per packet (inclusive of sorting costs), which improves upon all previously known schemes that guarantee delay and throughput fairness similar to WFQ. Interestingly, both the classical virtual clock and the self-clocked fair queuing schemes can be thought of as special cases of our scheme, by setting the leap forward parameter appropriately.

No abstract available.

We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally monotone $n \times n$ matrix whose entries represent shortest-path distances between pairs of vertices in a simple polygon. We apply this result to derive improved algorithms for several well-known problems in computational geometry. Most prominently, we obtain linear-time algorithms for computing the geodesic diameter, all farthest neighbors, and external farthest neighbors of a simple polygon, improving the previous best result by a factor of O(log n) in each case.

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over Rd for fixed d.

Article Stabbing triangulations by lines in 3D Share on Authors: Pankaj K. Agarwal Department of Computer Science, Box 90129, Duke University, Durham, NC Department of Computer Science, Box 90129, Duke University, Durham, NCView Profile , Boris Aronov Computer Science Department, Polytechnic University, Six MetroTech Center, Brooklyn, NY Computer Science Department, Polytechnic University, Six MetroTech Center, Brooklyn, NYView Profile , Subhash Suri Department of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MO Department of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MOView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 267–276https://doi.org/10.1145/220279.220308Online:01 September 1995Publication History 14citation354DownloadsMetricsTotal Citations14Total Downloads354Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We study some geometric maximization problems in the Euclidean plane under the non-crossing constraint. Given a set V of 2n points in general position in the plane, we investigate the following geometric configurations using straight-line segments an

Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries efficiently, the set of obstacle polyhedra is usually preprocessed into a data structure. In this paper we propose a query-sensitive data structure for ray shooting, which means that the performance of our data structure depends on the local geometry of obstacles near the query segment. We measure the complexity of the local geometry near the segment by a parameter called the simple cover complexity, denoted by scc(s) for a segment s. Our data structure consists of a subdivision that partitions the space into a collection of polyhedral cells, each of O(1) complexity. We answer a segment shooting query by walking along the segment through the subdivision. Our first result is that, for any fixed dimension d, there exists a simple hierarchical subdivision in which no query segment s intersects more than O(scc(s)) cells. Our second result shows that in two dimensions such a subdivision of size O(n) can be constructed in time O(n log n), where n is the total number of vertices in all the obstacles.

Current standards reserve one bit in the ATM cell header to indicate loss priority. When congestion occurs at a queue lower priority cells can be discarded in order to insure a smaller cell loss rate for higher priority cells. Strategies for determining which cells to discard are termed space priority buffer management schemes. In this paper two adjustable space priority schemes are studied where a cell upon arriving to a full buffer can pushout a cell of opposite priority depending upon an adjustable parameter. A queueing analysis of an ATM switching node is conducted to compare the adjustable pushout schemes with other common space priority mechanisms.>

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G={G1,G2,...,Gk} is called a clique cover of G if (i) each Gi is a clique or a bipartite clique, and (ii) the union of Gi is G. The size of the clique cover G is defined as Σki=1 ni, where ni is the number of vertices in Gi. Our main result is that there exist visibility graphs of n nonintersecting line segments in the plane whose smallest clique cover has size Ω(n2/log2n. An upper bound of 0(n2/log n) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of size O(n log3 n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n log n).

We study some geometric maximization problems in the Euclidean plane under the non-crossing constraint. Given a set V of 2n points in general position in the plane, we investigate the following geometric configurations using straight-line segments and the Euclidean norm: (i) longest non-crossing matching, (ii) longest non-crossing hamiltonian path, (iii) longest non-crossing spanning tree. We propose simple and efficient algorithms to approximate these structures within a constant factor of optimality. Somewhat surprisingly, we also show that our bounds are within a constant factor of optimality even without the non-crossing constraint. For instance, we give an algorithm to compute a non-crossing matching whose total length is at least 2/π of the longest (possibly crossing) matching, and show that the ratio 2/π between the non-crossing and crossing matching is the best possible. Perhaps due to their utter simplicity, our methods also seem more general and amenable to applications in other similar contexts.

We propose a new algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(nlog/sup 2/ n) and requires O(nlog n) space, where n is the total number of vertices in the obstacle polygons. Our algorithm actually computes a planar map that encodes shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previous results known for the shortest path problem.>

We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally-monotone n \\Theta n matrix whose entries represent shortest-path distances between pairs of vertices in a simple polygon. We apply this result to derive improved algorithms for several well-known problems in computational geometry. Most prominently, we obtain linear-time algorithms for computing the geodesic diameter, all farthest neighbors, and external farthest neighbors of a simple polygon, improving the previous best result by a factor of O(logn) in each case. Key Words: Shortest paths, matrix searching, geodesic diameter, farthest neighbors, geometric matching. 1 1 Introduction Matrix-searching is the popular term for a technique introduced by Aggarwal et al. [2] for computing row-wise maxima in a totally monotone matrix. A matrix M is called totally monotone if M(i; k) ! M(i; l) =) M(j; k) ! M(j; l); for any i ! j and k ! l. Aggarwal et al. [2] discovered the importance o...

We study some combinatorial and algorithmic problems related to transitions in Euclidean minimum spanning trees arising from an arbitrary motion of one or more points of the input set.3.

Let P be (the boundary of) a simple polygon with n vertices. For a vertex p of P, let ϕ(p) be the set of points on P that are farthest from p, where the distance between two points is the length of the (Euclidean) shortest path that connects them without intersecting the interior of P. In this paper, we present an O(n log n) algorithm to compute a member of ϕ(p) for every vertex p of P. As a corollary, the external diameter of P can also be computed in the same time.

Let S be a set, f : S × S → R + a bivariate function, and f ( x , S ) the maximum value of f ( x , y ) over all elements y ∈ S . We say that f is decomposable with respect with the maximum if f ( x , S ) = max { f ( x , S 1 ), f ( x , S 2 ),…, f ( x , S k )} for any decomposition S = ∪ i =1 i = k S i . Computing the maximum (minimum) value of a decomposable function is inherent in many problems of computational geometry and robotics. In this paper, a general technique is presented for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S . Our result holds for a semi-online model of dynamization: When an element is inserted, we are told how long it will stay. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) retangles determined by a set of points. These problems are fundamental to application areas such as robotics, VLSI masking, and optimization.

Given a set P of $2n$ points on the boundary of a polygon, consider the complete graph whose vertex set is P, and whose edges are assigned weights equal to the Euclidean distance between their endpoints if the endpoints see each other in the polygon and $ + \infty $ otherwise. The problem of finding a minimum-weightperfect matching is investigated in this graph, and an $O(n\log (n))$ time algorithm is obtained if the polygon is convex; an $O(n\log ^2 (n))$ time algorithm is obtained if the polygon is simple but not convex. Similar results are obtained for the assignment problem and the maximum-weight problem.

We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo [Me1]. The expected running time of our algorithm is Ο(n4/3 log 8/3 n). A deterministic version of our procedure runs in time Ο(n3/2 log5/2 n). Both versions improve the previously best known upper bound of Ο(n9/5 log4/5 n) by Chazelle [Ch]. A simple Ο(n log n) time algorithm for computing an approximation of the median distance is also presented.

Notation and a theorem are presented which, using a result of B. Chazelle and L.J. Guibas (1985), enable the authors to design an O(n log n) algorithm for reporting all visibility edges of a given n-vertex polygon. Improving on this bound to O(n) is presently focused upon. This problem is solved for polygons with at least one given visibility edge. It is assumed that both endpoints of this edge are convex vertices. Subsequently, it is shown how to drop this restriction. The general case of detecting weak edge visibility of an arbitrary simple polygon is dealt with.>

A technique is presented for preprocessing a simple polygon to answer link distance queries. The preprocessing requires linear time and the time to triangulate the polygon, and it uses linear storage. As an application of the technique, optimal algorithms for several fundamental link distance problems are derived.>

Article Free Access Share on Fining k points with minimum spanning trees and related problems Authors: A. Aggarwal IBM T. J. Watson Research Center IBM T. J. Watson Research CenterView Profile , H. Imai Kyushu University, Japan Kyushu University, JapanView Profile , N. Katoh Kobe University of Commerce, Japan Kobe University of Commerce, JapanView Profile , S. Suri Bell Communications Research Bell Communications ResearchView Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 283–291https://doi.org/10.1145/73833.73865Published:05 June 1989Publication History 7citation660DownloadsMetricsTotal Citations7Total Downloads660Last 12 Months14Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the following problem: given a planar set of points S, a measure μ acting on S, and a pair of values μ1 and μ2, does there exist a bipartition S = S1 U S2 satisfying μ(Si) ≤ μi for i = 1,2? We present algorithms of complexity Ο(n log n) for several natural measures, including the diameter (set measure), the area, perimeter or diagonal of the smallest enclosing axes-parallel rectangle (rectangular measure), and the side length of the smallest enclosing axes-parallel square (square measure). The problem of partitioning S into k subsets, where k ≥ 3, is known to be NP-complete for many of these measures.

An Ο(n3/2√α(n)) time algorithm is presented for finding a minimum-weight matching of a set of 2n points lying on the boundary of a convex polygon, where α(n) is the functional inverse of the Ackerman's function. Generalizing this result, we obtain an Ο(n3/2 logn√α(n)) time algorithm for the minimum-weight matching of points lying on the boundary of a simple nonconvex polygon, where we require that the line segments joining the matched pairs be contained within the polygon. We also consider the maximum-weight matching problem, and obtain algorithms of complexities Ο(n) and Ο(n log n) for the convex and the nonconvex case, respectively. By contrast, finding a weighted matching of an arbitrary set of points takes Ο(n5/2 log4 n) time [Vaidya 1987].

The authors present a general technique for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) rectangles determined by a set of points. The main appeal of the approach lies in its generality. Several research directions suggested by the work are noted.>

The complete graph induced by a set of 2n points on the boundary of a polygon is considered. The edges are assigned weights equal to the Euclidean distance between their endpoints if the endpoints see each other in the polygon, and + infinity otherwise. An O(n log n)-time algorithm is obtained for finding a minimum-weight perfect matching in this graph if the polygon is convex, and an O(n log/sup 2/n)-time algorithm if the polygon is simple but nonconvex. The assignment problem for a convex polygon is solved in time O(n log n), and O(n alpha (n)) and O(n alpha (n) log n) time bounds are obtained for the verification problem on convex and nonconvex polygons, respectively, where alpha (n) is the functional inverse of the Ackermann function.>

An algorithm is presented for finding a maximum-weight spanning tree of a set of n points in the Euclidean plane, where the weight of an edge (pi, pj) equals the Euclidean distance between the points pi and pj. The algorithm runs in time Ο (n logn) and requires Ο (n) space. If the points are vertices of a convex polygon (given in order along the boundary), then our algorithm requires only a linear amount of time and space. These bounds are the best possible in the algebraic computation-tree model. We also establish various properties of maximum spanning trees that can be exploited to solve other geometric problems.

We provide two algorithms for solving the following problem: Given a rectangle containing n points, compute the largest-area and the largest-perimeter subrectangles with sides parallel to the given rectangle that lie within this rectangle and that do not contain any points in their interior. For finding the largest-area empty rectangle, the first algorithm takes Ο(n log3 n) time and Ο(n) memory space and it simplifies the algorithm given by Chazelle, Drysdale and Lee which takes Ο(n log3 n) time but Ο(n log n) storage. The second algorithm for computing the largest-area empty rectangle is more complicated but it only takes Ο(n log2 n) time and Ο(n) memory space. The two algorithms for computing the largest-area rectangle can be modified to compute the largest-perimeter rectangle in Ο(n log2 n) and Ο(n log n) time, respectively. Since Ω(n log n) is a lower bound on time for computing the largest-perimeter empty rectangle, the second algorithm for computing such a rectangle is optimal within a multiplicative constant.

The link center of a simple polygon P is the set of points x inside P at which the maximal link-distance from x to any other point in P is minimized, where the link distance between two points x, y inside P is defined as the smallest number of straight edges in a polygonal path inside P connecting x to y. We prove several geometric properties of the link center and present an algorithm that calculates this set in time Ο (n2), where n is the number of sides of P. We also give an Ο(n log n) algorithm for finding a point x in an approximate link center, namely the maximal link distance from x to any point in P is at most one more than the value attained from the link center.

We present an O(n logn) time and O (n) space algorithm for the following problem in a simple polygon P with n vertices: For each vertex u of P, find another vertex p(u) that is furthest from u, where the distance between two points is measured by the length of the shortest internal path connecting them in P. As a corollary, the longest internal path in P, called the geodesic diameter, also can be found within the same time and space bound. All the previously known algorithms for computing the geodesic diameter have required O(n2) time in the worst case, e.g. see Chazelle [5], Reif and Storer [16] and Toussaint [19].

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an Ο(nlogκ) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and κ is the number of vertices of a minimal nested polygon. We also present an Ο(n) sub-optimal algorithm, and a simple Ο(nk) optimal algorithm.