Let K be a compact, centrally-symmetric, strictly-convex region in ℝ³, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as ‖⋅‖_K. Let 𝒦 be a set of n homothetic copies of K. This paper contains two main sets of results: (i) For a storage parameter s ∈ [n,n³], 𝒦 can be preprocessed in O^*(s) expected time into a data structure of size O^*(s), so that for a query homothet K₀ of K, an intersection-detection query (determine whether K₀ intersects any member of 𝒦, and if so, report such a member) or a nearest-neighbor query (return the member of 𝒦 whose ‖⋅‖_K-distance from K₀ is smallest) can be answered in O^*(n/s^{1/3}) time; all k homothets of 𝒦 intersecting K₀ can be reported in additional O(k) time. In addition, the data structure supports insertions/deletions in O^*(s/n) amortized expected time per operation. Here the O^*(⋅) notation hides factors of the form n^ε, where ε > 0 is an arbitrarily small constant, and the constant of proportionality depends on ε. (ii) Let 𝒢(𝒦) denote the intersection graph of 𝒦. Using the above data structure, breadth-first or depth-first search on 𝒢(𝒦) can be performed in O^*(n^{3/2}) expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of 𝒦 can be solved in O^*(n^{62/39}) expected time. Dijkstra’s shortest-path algorithm, as well as Prim’s MST algorithm, on a ‖⋅‖_K-proximity graph on n points in ℝ³, with edges weighted by ‖⋅‖_K, can also be performed in O^*(n^{3/2}) time.

We study various nearest-neighbor searching problems involving points, lines, segments and triangles in ℝ³. Among many results, we present a linear-size data structure for answering nearest-neighbor queries with lines amid n points in ℝ³, in O^*(n^{1/2}) time per query (where the O^*(⋅) notation hides subpolynomial factors). Our solution is based on parametric search, where the problem is reduced to range emptiness queries amid points in ℝ³ with cylindrical queries. For the latter problem we show that reporting all k points lying inside a cylinder query costs an additional term of O(k). We also study setups where both data and query objects are lines, segments, or triangles, and obtain improved solutions for the two extreme regimes of (near-)linear storage and of fast query time. These results also yield tradeoff bounds, where the cost of a query depends on the storage allocated to the structure. This work is a continuation of a recent work by the authors [Pankaj K. Agarwal et al., 2024].

We give the first (relative) (1+ε)-approximation algorithm for the continuous optimal transport (OT) problem between two axis-aligned histograms in the plane, each of which is represented as a piecewise-constant function over a rectangular subdivision. Our algorithm runs in nearly quadratic time in the complexity of the histograms in the worst case. In contrast to the discrete and semi-discrete optimal transport problems, which always admit linear-size OT plans, we demonstrate that there is a quadratic lower bound on the complexity of even a (1+ε)-approximate OT plan in the continuous setting in the worst case. This suggests that the runtime of our approximation algorithm nearly matches the worst-case lower-bound complexity of an explicit (1+ε)-approximate OT plan between two histograms. We additionally provide near-linear time algorithms with either weaker approximation guarantees or restrictions on the input histograms.

We present an algorithm that, given \(m\) points and \(n\) disks in \(\mathbb{R}^2\), computes the disk that contains the maximum number of points. The algorithm runs in \(O^*(m^{2/3} n^{2/3} + m^{32/59} n^{145/177} + m + n)\) expected time, where the \(O^*(\cdot)\) notation hides factors of the form \(n^\varepsilon\), for an arbitrarily small \(\varepsilon \gt 0\), and coefficients that depend on \(\varepsilon\). The algorithm is faster than existing algorithms for \(m \lt n^{5/4}\), and it has similar performance bounds for \(m \ge n^{5/4}\). As a matter of fact, except for disks that are fully contained in other disks, the algorithm counts the number of input points in each disk.

Let \(\mathscr{W} \subset \mathbb{R}^2\) be a planar polygonal environment with n vertices, and let \([k] = \{1, \ldots, k\}\) denote \(k\) unit-square robots translating in \(\mathscr{W}\). Given source and target placements \(s_1, t_1, \ldots, s_k, t_k, \in \mathscr{W}\) for each robot, we wish to compute a collision-free motion plan \(\boldsymbol \pi\), i.e., a coordinated motion for each robot \(i\) along a continuous path from \(s_i\) to \(t_i\), so that robot \(i\) does not leave \(\mathscr{W}\) or collide with any other robot \(j\). Moreover, we additionally require that \(\boldsymbol \pi\) minimizes the sum of the path lengths; this variant is known as min-sum motion planning.

We study the problem of computing the L₁-distance between two piecewise-linear bivariate functions f and g, defined over a bounded polygonal domain 𝕄 ⊂ ℝ², that is, computing the quantity ‖f-g‖₁ = ∫_𝕄 |f(x,y)-g(x,y)| dx dy. If f and g are defined by linear interpolation over triangulations 𝐓_f and 𝐓_g, respectively, of 𝕄 with a total of n triangles, we show that ‖f-g‖₁ can be computed in Õ(n^α) time, where α = max{(ω+1)/2, 8/5}, ω is the matrix multiplication exponent, and Õ notation hides factors of the form n^ε for any ε > 0. This bound holds for the currently best known value of ω, which is approximately 2.37. More generally, if the complexity of the overlay of 𝐓_f and 𝐓_g is κ, then the runtime of our algorithm is Õ(κ^{α-1}n^{2-α}).

The ability to acquire high-resolution, large-scale geospatial data at an unprecedented using LiDAR and other related technologies has intensified the need for scalable algorithms for terrain analysis, including shortest-path-distance (SPD) queries on large-scale terrain digital elevation models (DEMs). In this paper, we present a neural data structure for efficiently answering SPD queries approximately on a large terrain DEM, which is based on the recently proposed neural geodesic field (NeuroGF) framework (Zhang et al., 2023)—the state-of-the-art neural data structure for estimating geodesic distance. In particular, we propose a decoupled-NeuroGF data structure combined with an efficient two-stage mixed-training strategy, which significantly reduces computational bottlenecks and enables efficient training on terrain DEMs at a scale not feasible before. We demonstrate the efficacy of our approach by performing detailed experiments on both synthetic and real data sets. For instance, we can train a small model with around 70000 parameters on a terrain DEM with 16 million nodes in a matter of hours that can answer SPD queries with 1% relative error in at most 10ms per query.

The sensitivity of optimal transport (OT) to noise has motivated the study of robust variants. In this paper, we study two such formulations of semi-discrete OT in $\mathbb{R}^d$: (i) the $\alpha$-optimal partial transport, which minimizes the cost of transporting a mass of $\alpha$; and (ii) the $\lambda$-robust optimal transport, which regularizes the OT problem using the total variation (TV) distance. First, we provide a novel characterization of the optimal solutions in these settings, showing they can be represented as a restricted Laguerre diagram. Second, we exploit this characterization to establish a strong algorithmic connection between the two problems, showing that any solver for one can be adapted to solve the other with comparable precision. Third, we overcome key challenges posed in extending the cost-scaling paradigm to compute these variants of OT and present an algorithm that computes the exact solution up to $\log (1/\varepsilon)$ bits of precision in $n^{O(d)}\log (1/\varepsilon)$ time, where $n$ is the support size of the discrete distribution. Finally, we present an $n^{1+o(1)}\varepsilon^{-O(d)}$ time approximation algorithm for the above variants of OT.

Given a set of probability distributions, the Wasserstein barycenter problem asks to compute a distribution that minimizes the average Wasserstein distance, or optimal transport cost, from all the input distributions. Wasserstein barycenters preserve common geometric features of the input distributions, making them useful in machine learning and data analytics tasks.

Let $$\mathscr {B}$$ be a set of n unit balls in $${\mathbb {R}}^3$$ . We present a linear-size data structure for storing $$\mathscr {B}$$ that can determine in $$O^*(\sqrt{n})$$ time whether a query line intersects any ball of $$\mathscr {B}$$ and report all k such balls in additional O(k) time. The data structure can be constructed in $$O(n\log n)$$ time. (The $$O^*(\cdot )$$ notation hides subpolynomial factors, e.g., of the form $$O(n^{{\varepsilon }})$$ , for arbitrarily small $${\varepsilon }> 0$$ , and their coefficients which depend on $${\varepsilon }$$ .) We also consider the dual problem: Let $$\mathscr {L}$$ be a set of n lines in $${\mathbb {R}}^3$$ . We preprocess $$\mathscr {L}$$ , in $$O^*(n^2)$$ time, into a data structure of size $$O^*(n^2)$$ that can determine in $$O(\log {n})$$ time whether a query unit ball intersects any line of $$\mathscr {L}$$ , or report all k such lines in additional O(k) time.

Query optimizers rely heavily on selectivity estimates to choose efficient execution plans, but inaccuracies in these estimates often result in poor query performance. We introduce Hint-QPT ( Hint s for Robust Q uery P erformance T uning), an interactive tool designed to help users diagnose and improve query performance. Hint-QPT proactively recommends robust plans that are resilient to uncertainty in selectivity estimates, identifies sensitive subqueries for which selectivity estimation errors greatly affect plan quality, and provides intuitive interfaces for targeted selectivity adjustments. Users can either choose the recommended robust plans for execution, or acquire additional statistics on the identified sensitive subqueries to tune query performance. Moreover, Hint-QPT visualizes the alternative execution plans and their costs under uncertainty, helping users to better understand their robustness.

Let \(\mathcal{T}\) be a set of \(n\) flat (planar) semi-algebraic regions in \(\mathbb{R}^{3}\) of constant complexity (e.g., triangles, disks), which we call plates . We wish to preprocess \(\mathcal{T}\) into a data structure so that for a query object \(\gamma\) , which is also a plate, we can quickly answer various intersection queries , such as detecting whether \(\gamma\) intersects any plate of \(\mathcal{T}\) , reporting all the plates intersected by \(\gamma\) , or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in \(\mathbb{R}^{3}\) ( arcs , for short), or (ii) the input objects are arcs and the query objects are plates in \(\mathbb{R}^{3}\) . Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if \(\mathcal{T}\) is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses \(O^{*}(n^{4/3})\) storage (where the \(O^{*}(\cdot)\) notation hides factors of the form \(n^{\varepsilon}\) , for an arbitrarily small \(\varepsilon>0\) ) and answers an arc-intersection query in \(O^{*}(n^{2/3})\) time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter \(s\in[n^{4/3},n^{t_{q}}]\) , where \({t_{q}}\geq 3\) is the number of real parameters needed to specify a query arc, the query time can be decreased to \(O^{*}((n/s^{1/{t_{q}}})^{\tfrac{2/3}{1-1/{t_{q}}}})\) by increasing the storage to \(O^{*}(s)\) . Our approach can be extended to many additional intersection-searching problems in three dimensions, even when the input or query objects are not flat.

Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the assembly partitioning sub-problem: Given a set \(A\) of parts, find a subset \(S\subset A\) , referred to as a subassembly, such that \(S\) can be rigidly translated to infinity along a prescribed direction without colliding with \(A\setminus S\) . While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called connected-assembly-partitioning , which additionally requires each of the two subassemblies, \(S\) and \(A\setminus S\) , to be connected. We obtain the following results. — We show that this problem is NP-complete, settling an open question posed by Wilson et al. 30 years ago, even when \(A\) consists of unit-grid squares (i.e., \(A\) is polyomino-shaped). For assemblies composed of polygons, we also show that deciding whether complete (dis)assembly is possible by repeatedly applying connected-assembly-partitioning, is NP-complete. Toward these results, we prove the NP-hardness of a new Planar 3-SAT variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest. — On the positive side, we give an \(O(2^{k}n^{2})\) -time fixed-parameter tractable algorithm (requiring low degree polynomial-time preprocessing) for an assembly \(A\) consisting of polygons in the plane, where \(n=|A|\) and \(k=|S|\) . We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in \(O(n)\) -time.

Let $P$ be a set of $m$ points in ${\mathbb R}^2$, let $Σ$ be a set of $n$ semi-algebraic sets of constant complexity in ${\mathbb R}^2$, let $(S,+)$ be a semigroup, and let $w: P \rightarrow S$ be a weight function on the points of $P$. We describe a randomized algorithm for computing $w(P\capσ)$ for every $σ\inΣ$ in overall expected time $O^*\bigl( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr)$, where $s>0$ is a constant that bounds the maximum complexity of the regions of $Σ$, and where the $O^*(\cdot)$ notation hides subpolynomial factors. For $s\ge 3$, surprisingly, this bound is smaller than the best-known bound for answering $m$ such queries in an on-line manner. The latter takes $O^*(m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}+m+n)$ time. Let $Φ: Σ\times P \rightarrow \{0,1\}$ be the Boolean predicate (of constant complexity) such that $Φ(σ,p) = 1$ if $p\inσ$ and $0$ otherwise, and let $Σ\mathopΦ P = \{ (σ,p) \in Σ\times P \mid Φ(σ,p)=1\}$. Our algorithm actually computes a partition ${\mathcal B}_Φ$ of $Σ\mathopΦ P$ into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) $O^*\bigl( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr)$. It is straightforward to compute $w(P\capσ)$ for all $σ\in Σ$ from ${\mathcal B}_Φ$. Similarly, if $η: Σ\rightarrow S$ is a weight function on the regions of $Σ$, $\sum_{σ\in Σ: p \in σ} η(σ)$, for every point $p\in P$, can be computed from ${\mathcal B}_Φ$ in a straightforward manner. A recent work of Chan et al. solves the online version of this dual point enclosure problem within the same performance bound as our off-line solution. We also mention a few other applications of computing ${\mathcal B}_Φ$.

We are given a set $\mathcal{Z}=\{(R_1,s_1),\ldots, (R_n,s_n)\}$, where each $R_i$ is a \emph{range} in $\Re^d$, such as rectangle or ball, and $s_i \in [0,1]$ denotes its \emph{selectivity}. The goal is to compute a small-size \emph{discrete data distribution} $\mathcal{D}=\{(q_1,w_1),\ldots, (q_m,w_m)\}$, where $q_j\in \Re^d$ and $w_j\in [0,1]$ for each $1\leq j\leq m$, and $\sum_{1\leq j\leq m}w_j= 1$, such that $\mathcal{D}$ is the most \emph{consistent} with $\mathcal{Z}$, i.e., $\mathrm{err}_p(\mathcal{D},\mathcal{Z})=\frac{1}{n}\sum_{i=1}^n\! \lvert{s_i-\sum_{j=1}^m w_j\cdot 1(q_j\in R_i)}\rvert^p$ is minimized. In a database setting, $\mathcal{Z}$ corresponds to a workload of range queries over some table, together with their observed selectivities (i.e., fraction of tuples returned), and $\mathcal{D}$ can be used as compact model for approximating the data distribution within the table without accessing the underlying contents. In this paper, we obtain both upper and lower bounds for this problem. In particular, we show that the problem of finding the best data distribution from selectivity queries is $\mathsf{NP}$-complete. On the positive side, we describe a Monte Carlo algorithm that constructs, in time $O((n+δ^{-d})δ^{-2}\mathop{\mathrm{polylog}})$, a discrete distribution $\tilde{\mathcal{D}}$ of size $O(δ^{-2})$, such that $\mathrm{err}_p(\tilde{\mathcal{D}},\mathcal{Z})\leq \min_{\mathcal{D}}\mathrm{err}_p(\mathcal{D},\mathcal{Z})+δ$ (for $p=1,2,\infty$) where the minimum is taken over all discrete distributions. We also establish conditional lower bounds, which strongly indicate the infeasibility of relative approximations as well as removal of the exponential dependency on the dimension for additive approximations. This suggests that significant improvements to our algorithm are unlikely.

Optimal Transport (OT, also known as the Wasserstein distance) is a popular metric for comparing probability distributions and has been successfully used in many machine-learning applications. In the semi-discrete $2$-Wasserstein problem, we wish to compute the cheapest way to transport all the mass from a continuous distribution $\mu$ to a discrete distribution $\nu$ in $\mathbb{R}^d$ for $d\ge 1$, where the cost of transporting unit mass between points $a$ and $b$ is $d(a,b)=||a-b||^2$. When both distributions are discrete, a simple combinatorial framework has been used to find the exact solution (see e.g. [Orlin, STOC 1988]). In this paper, we propose a combinatorial framework for the semi-discrete OT, which can be viewed as an extension of the combinatorial framework for the discrete OT but requires several new ideas. We present a new algorithm that given $\mu$ and $\nu$ in $\mathbb{R}^2$ and a parameter $\varepsilon>0$, computes an $\varepsilon$-additive approximate semi-discrete transport plan in $O(n^{4}\log n\log \frac{1}{\varepsilon})$ time (in the worst case), where $n$ is the support-size of the discrete distribution $\nu$ and we assume that the mass of $\mu$ inside a triangle can be computed in $O(1)$ time. Our algorithm is significantly faster than the known algorithms, and unlike many numerical algorithms, it does not make any assumptions on the smoothness of $\mu$. As an application of our algorithm, we describe a data structure to store a large discrete distribution $\mu$ (with support size $N$) using $O(N)$ space so that, given a query discrete distribution $\nu$ (with support size $k$), an $\varepsilon$-additive approximate transport plan can be computed in $O(k^{3}\sqrt{N}\log \frac{1}{\varepsilon})$ time in $2$ dimensions. Our algorithm and data structure extend to higher dimensions as well as to $p$-Wasserstein problem for any $p \ge 1$.

Vertical decomposition is a widely used general technique for decomposing the cells of arrangements of semi-algebraic sets in ℝd into constant-complexity subcells. In this paper, we settle in the affirmative a few long-standing open problems involving the vertical decomposition of substructures of arrangements for d = 3,4: (i) Let S be a collection of n semi-algebraic sets of constant complexity in ℝ3, and let U(m) be an upper bound on the complexity of the union U(S‘) of any subset S’ ⊆ S of size at most m. We prove that the complexity of the vertical decomposition of the complement of U(S) is O* (n2 + U(n)) (where the O* (·) notation hides subpolynomial factors). We also show that the complexity of the vertical decomposition of the entire arrangement A(S) is O*(n2 + X), where X is the number of vertices in A(S). (ii) Let F be a collection of n trivariate functions whose graphs are semi-algebraic sets of constant complexity. We show that the complexity of the vertical decomposition of the portion of the arrangement A(F) in ℝ4 lying below the lower envelope of F is O*(n3).

Let B = (b1,…, bn} be a set of n axis-aligned boxes in ℝd where d ≥ 2 is a constant. The piercing problem is to compute a smallest set of points N ∪ ℝd that hits every box in B, i.e., N ∩ bi ≠ ϕ, for i = 1,…, n. The problem is known to be NP-Hard. Let p := p (B), the piercing number be the minimum size of a piercing set of B. We first present a randomized O(log log p)-approximation algorithm with expected running time O(nd/2 polylog(n)). Next, we show that the expected running time can be improved to near-linear using a sampling-based technique, if p = O(n1/(d-1)). Specifically, in the plane, the improved running time is O(n log p), assuming p < n/ logΩ(1) n. Finally, we study the dynamic version of the piercing problem where boxes can be inserted or deleted. For boxes in ℝ2, we obtain a randomized O(log log p)-approximation algorithm with O(n1/2 polylog(n)) amortized expected update time for insertion or deletion of boxes. For squares in ℝ2, the update time can be improved to O(n1/3 polylog(n)).

Let W ⊂ ℝ2 be a planar polygonal environment (i.e., a polygon potentially with holes) with a total of n vertices, and let A, B be two robots, each modeled as an axis-aligned unit square, that can translate inside W. Given source and target placements sA,tA,sB, tB ∈ W of A and B, respectively, the goal is to compute a collision-free-motion plan π*, i.e., a motion plan that continuously moves A from sA to tA and B from sB to tB so that A and B remain inside W and do not collide with each other during the motion. Furthermore, if such a plan exists, then we wish to return a plan that minimizes the sum of the lengths of the paths traversed by the robots. Given W,sA,tA,sB,tB and a parameter ɛ > 0, we present an n2ɛ-°(1) log n-time (1 + ɛ)-approximation algorithm for this problem. We are not aware of any polynomial-time algorithm for this problem, nor do we know whether the problem is NP-Hard. Our result is the first polynomial-time (1 + ɛ)-approximation algorithm for an optimal motion-planning problem involving two robots moving in a polygonal environment.

Given a d-dimensional continuous (resp. discrete) probability distribution μ and a discrete distribution ν, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from μ to ν; we assume n to be the number of points in the support of the discrete distributions. In this paper, we present three approximation algorithms for the OT problem with strong provable guarantees.

Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in ℝ², and let ϱ: S× S → ℝ_{≥ 0} be a distance function on S. For a parameter r ≥ 0, we define the proximity graph G(r) = (S,E) where E = {(e₁,e₂) ∈ S×S ∣ e₁≠e₂, ϱ(e₁,e₂) ≤ r}. Given S, s,t ∈ S, and an integer k ≥ 1, the reverse-shortest-path (RSP) problem asks for computing the smallest value r^* ≥ 0 such that G(r^*) contains a path from s to t of length at most k. In this paper we present a general randomized technique that solves the RSP problem efficiently for a large family of geometric objects and distance functions. Using standard, and sometimes more involved, semi-algebraic range-searching techniques, we first give an efficient algorithm for the decision problem, namely, given a value r ≥ 0, determine whether G(r) contains a path from s to t of length at most k. Next, we adapt our decision algorithm and combine it with a random-sampling method to compute r^*, by efficiently performing a binary search over an implicit set of O(n²) candidate values that contains r^*. We illustrate the versatility of our general technique by applying it to a variety of geometric proximity graphs. For example, we obtain (i) an O^*(n^{4/3}) expected-time randomized algorithm (where O^*(⋅) hides polylog(n) factors) for the case where S is a set of pairwise-disjoint line segments in ℝ² and ϱ(e₁,e₂) = min_{x ∈ e₁, y ∈ e₂} ‖x-y‖ (where ‖⋅‖ is the Euclidean distance), and (ii) an O^*(n+m^{4/3}) expected-time randomized algorithm for the case where S is a set of m points lying on an x-monotone polygonal chain T with n vertices, and ϱ(p,q), for p,q ∈ S, is the smallest value h such that the points p' := p+(0,h) and q' := q+(0,h) are visible to each other, i.e., all points on the segment p'q' lie above or on the polygonal chain T.

Data summarization is a powerful approach to deal with large-scale data analytics, which has wide applications in web search, recommendation systems, approximate query processing, etc. It computes a small, compact summary that preserves vital properties of the original data. In this paper, we study the data summarization problem of conjunctive query results, i.e., computing a k-size subset of a conjunctive query output, for any given k>0, that optimizes a certain objective. More specifically, we are interested in two commonly studied objectives: cohesion, which measures the maximum distance between a tuple in the query result tuples and its closest tuple in the summary (k-center clustering); and diversity, which measures the pairwise distances between the summary items. A simple approach that computes the entire query output and then applies existing algorithms on top of these materialized tuples suffers from high computational complexity because the query output can be large, e.g., for a relational database of N tuples, the number of result tuples can be N O(1). We propose O(1)-approximation algorithms that compute well-representative summaries of size k in time O(N*k O(1) ), or even O(N+ k O(1) ) in some cases, without computing all result tuples. We also propose the first efficient (2+\eps)-approximation algorithm for the k-center clustering problem over relational data. Our main idea is to formulate a few oracles that enable us to access specific query result tuples with certain properties, to show how these oracles can be implemented efficiently, and to compute desired summaries with few invocations of these oracles.

Finding patterns in graphs is a fundamental problem in databases and data mining. In many applications, graphs are temporal and evolve over time, so we are interested in finding durable patterns, such as triangles and paths, which persist over a long time. While there has been work on finding durable simple patterns, existing algorithms do not have provable guarantees and run in strictly super-linear time. The paper leverages the observation that many graphs arising in practice are naturally proximity graphs or can be approximated as such, where nodes are embedded as points in some high-dimensional space, and two nodes are connected by an edge if they are close to each other. We work with an implicit representation of the proximity graph, where nodes are additionally annotated by time intervals, and design near-linear-time algorithms for finding (approximately) durable patterns above a given durability threshold. We also consider an interactive setting where a client experiments with different durability thresholds in a sequence of queries; we show how to compute incremental changes to result patterns efficiently in time near-linear to the size of the changes.

The effectiveness of a query optimizer relies on the accuracy of selectivity estimates. The execution plan generated by the optimizer can be extremely poor in reality due to uncertainty in these estimates. This paper presents PARQO ( P enalty- A ware R obust Plan Selection in Q uery O ptimization), a novel system where users can define powerful robustness metrics that assess the expected penalty of a plan with respect to true optimal plans under uncertain selectivity estimates. PARQO uses workload-informed profiling to build error models, and employs principled sensitivity analysis techniques to identify human-interpretable selectivity dimensions with the largest impact on penalty. Experiments on three benchmarks demonstrate that PARQO finds robust, performant plans, and enables efficient and effective parametric optimization.

Let $P$ be a set of $n$ points in $\Re^2$. For a parameter $\varepsilon\in (0,1)$, a subset $C\subseteq P$ is an \emph{$\varepsilon$-kernel} of $P$ if the projection of the convex hull of $C$ approximates that of $P$ within $(1-\varepsilon)$-factor in every direction. The set $C$ is a \emph{weak $\varepsilon$-kernel} of $P$ if its directional width approximates that of $P$ in every direction. Let $\mathsf{k}_{\varepsilon}(P)$ (resp.\ $\mathsf{k}^{\mathsf{w}}_{\varepsilon}(P)$) denote the minimum-size of an $\varepsilon$-kernel (resp. weak $\varepsilon$-kernel) of $P$. We present an $O(n\mathsf{k}_{\varepsilon}(P)\log n)$-time algorithm for computing an $\varepsilon$-kernel of $P$ of size $\mathsf{k}_{\varepsilon}(P)$, and an $O(n^2\log n)$-time algorithm for computing a weak $\varepsilon$-kernel of $P$ of size ${\mathsf{k}}^{\mathsf{w}}_{\varepsilon}(P)$. We also present a fast algorithm for the Hausdorff variant of this problem. In addition, we introduce the notion of \emph{$\varepsilon$-core}, a convex polygon lying inside $\mathsf{ch}(P)$, prove that it is a good approximation of the optimal $\varepsilon$-kernel, present an efficient algorithm for computing it, and use it to compute an $\varepsilon$-kernel of small size.

We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition P of the plane into regions so that each region contains roughly s = n/k points. P should satisfy a notion of "local" fairness, which is related to the notion of core, a well-studied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in P if it belongs to the minority party. A group D of roughly s contiguous points is called a deviating group with respect to P if majority of points in D are unhappy in P. The partition P is locally fair if there is no deviating group with respect to P. This paper focuses on a restricted case when points lie in 1D. The problem is non-trivial even in this case. We consider both adversarial and "beyond worst-case" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are "runs" of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of s, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomial-time algorithm for computing a locally fair partition if one exists.

Let $\mathcal{T}$ be a set of $n$ flat (planar) semi-algebraic regions in $\mathbb{R}^3$ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess $\mathcal{T}$ into a data structure so that for a query object $γ$, which is also a plate, we can quickly answer various intersection queries, such as detecting whether $γ$ intersects any plate of $\mathcal{T}$, reporting all the plates intersected by $γ$, or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in $\mathbb{R}^3$ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in $\mathbb{R}^3$. Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if $\mathcal{T}$ is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses $O^*(n^{4/3})$ storage (where the $O^*(\cdot)$ notation hides factors of the form $n^ε$, for an arbitrarily small $ε>0$) and answers an arc-intersection query in $O^*(n^{2/3})$ time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter $s\in [n^{4/3}, n^{t_q}]$, where ${t_q}\ge 3$ is the number of real parameters needed to specify a query arc, the query time can be decreased to $O^*((n/s^{1/{t_q}})^{\tfrac{2/3}{1-1/{t_q}}})$ by increasing the storage to $O^*(s)$.

We study the problem of motion planning for a collection of $n$ labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radius $2$ disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a weakly-monotone motion plan, in which robots move according to an ordering as follows: during the turn of a robot $R$ in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As $R$ passes through a revolving area, a robot $R'$ that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time $(1+ε)$-approximation algorithm. On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an $O(1)$ factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time $O(\log n \log \log n)$-approximation algorithm for this problem.

In this paper, we propose to use the concept of local fairness for auditing and ranking redistricting plans. Given a redistricting plan, a deviating group is a population-balanced contiguous region in which a majority of individuals are of the same interest and in the minority of their respective districts; such a set of individuals have a justified complaint with how the redistricting plan was drawn. A redistricting plan with no deviating groups is called locally fair. We show that the problem of auditing a given plan for local fairness is NP-complete. We present an MCMC approach for auditing as well as ranking redistricting plans. We also present a dynamic programming based algorithm for the auditing problem that we use to demonstrate the efficacy of our MCMC approach. Using these tools, we test local fairness on real-world election data, showing that it is indeed possible to find plans that are almost or exactly locally fair. Further, we show that such plans can be generated while sacrificing very little in terms of compactness and existing fairness measures such as competitiveness of the districts or seat shares of the plans.

This paper explores the use of machine learning for estimating the selectivity of range queries in database systems. Using classic learning theory for real-valued functions based on shattering dimension, we show that the selectivity function of a range space with bounded VC-dimension is learnable. As many popular classes of queries (e.g., orthogonal range search, inequalities involving linear combination of attributes, distance-based search, etc.) represent range spaces with finite VC-dimension, our result immediately implies that their selectivity functions are also learnable. To the best of our knowledge, this is the first attempt at formally explaining the role of machine learning techniques in selectivity estimation, and complements the growing literature in empirical studies in this direction. Supplementing these theoretical results, our experimental results demonstrate that, empirically, even a basic learning algorithm with generic models is able to produce accurate predictions across settings, matching state-of-art methods designed for specific queries, and using training sample sizes commensurate with our theory.

This paper studies multi-way join queries over temporal data, where each tuple is associated with a valid time interval indicating when the tuple is valid. A temporal join requires that joining tuples' valid intervals intersect. Previous work on temporal joins has focused on joining two relations, but pairwise processing is often inefficient because it may generate unnecessarily large intermediate results. This paper investigates how to efficiently process complex temporal joins involving multiple relations. We also consider a useful extension, durable temporal joins, which further selects results with long enough valid intervals so they are not merely transient patterns.

Given two point sets A and B in ℝd of size n each, for some constant dimension d≥ 1, and a parameter ε>0, we present a deterministic algorithm that computes, in n·(ε−1 logn)O(d) time, a perfect matching between A and B whose cost is within a (1+ε) factor of the optimal matching under any ℓp-norm. Although a Monte-Carlo algorithm with a similar running time is proposed by Raghvendra and Agarwal [J. ACM 2020], the best-known deterministic ε-approximation algorithm takes Ω(n3/2) time. Our algorithm constructs a (refinement of a) tree cover of ℝd, and we develop several new tools to apply a tree-cover based approach to compute an ε-approximate perfect matching.

We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudo-lines in the plane. More precisely, we present three main results in this paper: (i) We present a linear-size data structure to maintain the union of a set of unit discs under insertions. It can insert a disc and update the union in O (( k +1)log 2 n ) time, where n is the current number of unit discs and k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. It can also compute, within the same time bound, the area of the union after the insertion of each disc. (ii) We propose a linear-size data structure for maintaining the lower envelope of a set of x -monotone pseudo-lines. It can handle insertion/deletion of a pseudo-line in O (log 2 n ) time; for a query point x 0 ∈ ℝ, it can report, in O (log n ) time, the point on the lower envelope with x -coordinate x 0 ; and for a query point q ∈ ℝ 2 , it can return all k pseudo-lines lying below q in time O (log n + k log 2 n ). (iii) We present a linear-size data structure for storing a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), so that for a query unit disc D , all input arcs intersecting D can be reported in O ( n 1/2+ɛ + k ) time, where k is the output size and ɛ > 0 is an arbitrarily small constant. A unit-circle arc can be inserted or deleted in O (log 2 n ) time.

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.

This paper considers enumerating answers to similarity-join queries under dynamic updates: Given two sets of $n$ points $A,B$ in $\mathbb{R}^d$, a metric $ϕ(\cdot)$, and a distance threshold $r > 0$, report all pairs of points $(a, b) \in A \times B$ with $ϕ(a,b) \le r$. Our goal is to store $A,B$ into a dynamic data structure that, whenever asked, can enumerate all result pairs with worst-case delay guarantee, i.e., the time between enumerating two consecutive pairs is bounded. Furthermore, the data structure can be efficiently updated when a point is inserted into or deleted from $A$ or $B$. We propose several efficient data structures for answering similarity-join queries in low dimension. For exact enumeration of similarity join, we present near-linear-size data structures for $\ell_1, \ell_\infty$ metrics with $\log^{O(1)} n$ update time and delay. We show that such a data structure is not feasible for the $\ell_2$ metric for $d \ge 4$. For approximate enumeration of similarity join, where the distance threshold is a soft constraint, we obtain a unified linear-size data structure for $\ell_p$ metric, with $\log^{O(1)} n$ delay and update time. In high dimensions, we present an efficient data structure with worst-case delay-guarantee using locality sensitive hashing (LSH).

A way of finding interesting or exceptional records from instant-stamped temporal data is to consider their "durability, " or, intuitively speaking, how well they compare with other records that arrived earlier or later, and how long they retain their supremacy. For example, people are naturally fascinated by claims with long durability, such as: "On January 22, 2006, Kobe Bryant dropped 81 points against Toronto Raptors. Since then, this scoring record has yet to be broken." In general, given a sequence of instant-stamped records, suppose that we can rank them by a user-specified scoring function f, which may consider multiple attributes of a record to compute a single score for ranking. This paper studies durable top-k queries, which find records whose scores were within top-k among those records within a "durability window" of given length, e.g., a 10-year window starting/ending at the timestamp of the record. The parameter k, the length of the durability window, and parameters of the scoring function (which capture user preference) can all be given at the query time. We illustrate why this problem formulation yields more meaningful answers in some practical situations than other similar types of queries considered previously. We propose new algorithms for solving this problem, and provide a comprehensive theoretical analysis on the complexities of the problem itself and of our algorithms. Our algorithms vastly outperform various baselines (by up to two orders of magnitude on real and synthetic datasets).

We consider a class of queries called durability prediction queries that arise commonly in predictive analytics, where we use a given predictive model to answer questions about possible futures to inform our decisions. Examples of durability prediction queries include "what is the probability that this financial product will keep losing money over the next 12 quarters before turning in any profit?" and "what is the chance for our proposed server cluster to fail the required service-level agreement before its term ends?" We devise a general method called Multi-Level Splitting Sampling (MLSS) that can efficiently handle complex queries and complex models---including those involving black-box functions---as long as the models allow us to simulate possible futures step by step. Our method addresses the inefficiency of standard Monte Carlo (MC) methods by applying the idea of importance splitting to let one "promising" sample path prefix generate multiple "offspring" paths, thereby directing simulation efforts toward more promising paths. We propose practical techniques for designing splitting strategies, freeing users from manual tuning. Experiments show that our approach is able to achieve unbiased estimates and the same error guarantees as standard MC while offering an order-of-magnitude cost reduction.

Assembly planning is a fundamental problem in robotics and automation, which aims to design a sequence of motions that brings the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected. In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set A of unit-grid squares in the plane, find a connected subset S ⊂ A such that A \ S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S. We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. a quarter of a century ago [16]. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O(2kn2)-time algorithm, where n = |A| and k = |S|. Second, we describe a special case of this problem where a connected partition can always be found in O(n) time.

Let be a set of n axis-aligned cubes of arbitrary sizes in ℝ3 in general position. Let ≔ be their union, and let κ be the number of vertices on ∂; κ can vary between O(1) and O(n2). We show that cl(ℝ3 \ ) can be decomposed into O(κ log4 n) axis-aligned boxes with pairwise-disjoint interiors. Given a boundary representation of , such a decomposition can be computed in O(n log2 n + κ log6 n) time. We also show that a decomposition of size O(σ log4 n + κ log2 n), where σ is the number of input cubes that appear on ∂, can be computed in O(n log2 n + σ log8 n + κ log6 n) time. The complexity and runtime bounds improve to O(n log n) if all cubes in are congruent.

In 2015, Guth proved that if $\EuScript{S}$ is a collection of $n$ $g$-dimensional semialgebraic sets in ${\mathbb{R}}^d$ and if $D\geq 1$ is an integer, then there is a $d$-variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $\EuScript{S}$. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently---the expected running time of our algorithm is linear in $\lvert \EuScript{S}\rvert$. Our approach exploits the technique of quantifier elimination combined with that of $\eps$-samples. We also present an extension of our construction to multilevel polynomial partitioning for semialgebraic sets in $\mathbb{R}^d$. We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semialgebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+\eps})$. The second is a data structure for answering range-searching queries with semialgebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+\eps})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semialgebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+\eps})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudosegments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$, where we show a nearly optimal algorithm to cut $n$ pairwise disjoint nonvertical triangles in ${\mathbb{R}}^3$ into pieces that form a depth order.

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.

An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this paper we study a number of flow-query related problems: given a terrain Σ represented as a triangulated xy-monotone surface with n vertices, and a rain distribution R which may vary over time, determine how much water is flowing over a given edge as a function of time. We develop internal-memory as well as I/O-efficient algorithms for flow queries. This paper contains four main results:

Let P be a set of n (non-negatively) weighted points in Rd. We consider the problem of computing a subset of (at most) k diverse and high-valued points of P that lie inside a query range, a problem relevant to many areas such as search engines, recommendation systems, and online stores. The diversity and value of a set of points are measured as functions (say average or minimum) of their pairwise distances and weights, respectively. We study both bicriteria and constrained optimization problems. In the former, we wish to return a set of k points that maximize a weighted sum of their value and diversity measures, and in the latter, we wish to return a set of at most k points that maximize their value and satisfy a diversity constraint. We obtain three main types of results in this paper: Near-linear time (0.5-ε)-approximation algorithms for the bicriteria optimization problem in the offline setting. Near-linear size indexes for the bicriteria optimization problem that for a query rectangle return a (0.5-ε)-approximate solution in time O(k polylog(n)). The indexes can be constructed in O(n polylog(n)) time. Near-linear size indexes for answering constrained optimization range queries. For a query rectangle, a 0.5O(d)-approximate solution can be computed in O(k polylog(n)) time. If we allow some of the returned points to lie at most ε outside of the query rectangle then an (1-ε)-approximate solution can be computed in O(k polylog(n)) time. The indexes are constructed in O(n polylog(n)) and nO(1/εd) time, respectively.

For point sets A , B ⊂ R d , ∣ A ∣ = ∣ B ∣ = n , and for a parameter ε > 0, we present a Monte Carlo algorithm that computes, in O ( n poly(log n , 1/ε)) time, an ε-approximate perfect matching of A and B under any L p -norm with high probability; the previously best-known algorithm takes Ω( n 3/2 ) time. We approximate the L p -norm using a distance function, d(⋅, ⋅) based on a randomly shifted quad-tree. The algorithm iteratively generates an approximate minimum-cost augmenting path under d(⋅, ⋅) in time proportional, within a polylogarithmic factor, to the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O ( n /ε)log n ), implying that the running time of our algorithm is O ( n poly(log n , 1/ε)).

In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d and if D >= 1 is an integer, then there is a d-variate polynomial P of degree at most D so that each connected component of R^d \ Z(P) intersects O(n/D^{d-g}) sets from S. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently - the expected running time of our algorithm is linear in |S|. Our approach exploits the technique of quantifier elimination combined with that of epsilon-samples. We present four applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in R^d in O(log n) time, with storage complexity and expected preprocessing time of O(n^{d+epsilon}). The second is a data structure for answering range search queries with semi-algebraic ranges in O(log n) time, with O(n^{t+epsilon}) storage and expected preprocessing time, where t > 0 is an integer that depends on d and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in R^{d} in O(log^2 n) time, with O(n^{d+epsilon}) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments.

We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of n unit discs under insertions in O(k log^2 n) update time and O(n) space, where k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has O(log^2 n) update time and O(log n) vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in O(log n) time, using tentative binary search; the lower envelopes are special in that at x=-infty any pseudo-line contributing to the first envelope lies below every pseudo-line contributing to the second envelope. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with O(n log n) preprocessing time, O(n^{1/2+epsilon} + l) query time and O(log^2 n) amortized update time, where l is the size of the output and for any epsilon>0. The structure requires O(n) storage space.

Let $A$ and $B$ be two point sets in the plane of sizes $r$ and $n$ respectively (assume $r \leq n$), and let $k$ be a parameter. A matching between $A$ and $B$ is a family of pairs in $A \times B$ so that any point of $A \cup B$ appears in at most one pair. Given two positive integers $p$ and $q$, we define the cost of matching $M$ to be $c(M) = \sum_{(a, b) \in M}\|{a-b}\|_p^q$ where $\|{\cdot}\|_p$ is the $L_p$-norm. The geometric partial matching problem asks to find the minimum-cost size-$k$ matching between $A$ and $B$. We present efficient algorithms for geometric partial matching problem that work for any powers of $L_p$-norm matching objective: An exact algorithm that runs in $O((n + k^2) {\mathop{\mathrm{polylog}}} n)$ time, and a $(1 + \varepsilon)$-approximation algorithm that runs in $O((n + k\sqrt{k}) {\mathop{\mathrm{polylog}}} n \cdot \log\varepsilon^{-1})$ time. Both algorithms are based on the primal-dual flow augmentation scheme; the main improvements involve using dynamic data structures to achieve efficient flow augmentations. With similar techniques, we give an exact algorithm for the planar transportation problem running in $O(\min\{n^2, rn^{3/2}\} {\mathop{\mathrm{polylog}}} n)$ time.

We study the optimization problem of selecting numerical quantities to clean in order to fact-check claims based on such data. Oftentimes, such claims are technically correct, but they can still mislead for two reasons. First, data may contain uncertainty and errors. Second, data can be "fished" to advance particular positions. In practice, fact-checkers cannot afford to clean all data and must choose to clean what "matters the most" to checking a claim. We explore alternative definitions of what "matters the most": one is to ascertain claim qualities (by minimizing uncertainty in these measures), while an alternative is just to counter the claim (by maximizing the probability of finding a counterargument). We show whether the two objectives align with each other, with important implications on when fact-checkers should exercise care in selective data cleaning, to avoid potential bias introduced by their desire to counter claims. We develop efficient algorithms for solving the various variants of the optimization problem, showing significant improvements over naive solutions. The problem is particularly challenging because the objectives in the fact-checking context are complex, non-linear functions over data. We obtain results that generalize to a large class of functions, with potential applications beyond fact-checking.

We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set $S$ of point sites in a static simple polygon $P$. Our data structure allows us to insert a new site in $S$, delete a site from $S$, and ask for the site in $S$ closest to an arbitrary query point $q \in P$. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in $P$. Our data structure achieves polylogarithmic update and query times, and uses $O(n\log^3n\log m + m)$ space, where $n$ is the number of sites in $S$ and $m$ is the number of vertices in $P$. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper we study a number of flood-risk related problems: Given a terrain Σ, represented as a triangulated xy-monotone surface with n vertices, a rain distribution R and a volume of rain ψ, determine which portions of Σ are flooded. We develop efficient algorithms for flood-risk analysis under the multiflow-directions (MFD) model, in which water at a point can flow along multiple downslope edges to more accurately represent flooding events.

Let T={triangle_1,...,triangle_n} be a set of of n pairwise-disjoint triangles in R^3, and let B be a convex polytope in R^3 with a constant number of faces. For each i, let C_i = triangle_i oplus r_i B denote the Minkowski sum of triangle_i with a copy of B scaled by r_i>0. We show that if the scaling factors r_1, ..., r_n are chosen randomly then the expected complexity of the union of C_1, ..., C_n is O(n^{2+epsilon), for any epsilon > 0; the constant of proportionality depends on epsilon and the complexity of B. The worst-case bound can be Theta(n^3). We also consider a special case of this problem in which T is a set of points in R^3 and B is a unit cube in R^3, i.e., each C_i is a cube of side-length 2r_i. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(n log^2 n), and it improves to O(n log n) if the scaling factors are chosen randomly from a "well-behaved" probability density function (pdf). We also extend the latter results to higher dimensions. For any fixed odd value of d, we show that the expected complexity of the union of the hypercubes is O(n^floor[d/2] log n) and the bound improves to O(n^floor[d/2]) if the scaling factors are chosen from a "well-behaved" pdf. The worst-case bounds are Theta(n^2) in R^3, and Theta(n^{ceil[d/2]}) in higher dimensions.

Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the L_p-norm of the tuple of the Euclidean distances between the pairs of matched points, for any p in [1,infty], and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.

We propose a model for subtrajectory clustering ---the clustering of subsequences of trajectories; each cluster of subtrajectories is represented as a pathlet, a sequence of points that is not necessarily a subsequence of an input trajectory. Given a set of trajectories, our clustering model attempts to capture the shared portions between them by assuming each trajectory is a concatenation of a small set of pathlets, with possible gaps in between. We present a single objective function for finding the optimal collection of pathlets that best represents the trajectories taking into account noise and other artifacts of the data. We show that the subtrajectory clustering problem is NP-Hard and present fast approximation algorithms for subtrajectory clustering. We further improve the running time of our algorithm if the input trajectories are "well-behaved." Finally, we present experimental results on both real and synthetic data sets. We show via visualization and quantitative analysis that the algorithm indeed handles the desiderata of being robust to variations, being efficient and accurate, and being data-driven.

Many datasets have a temporal dimension and contain a wealth of historical information. When using such data to make decisions, we often want to examine not only the current snapshot of the data but also its history. For example, given a result object of a snapshot query, we can ask for its "durability," or intuitively, how long (or how often) it was valid in the past. This paper considers durable top-k queries, which look for objects whose values were among the top k for at least some fraction of the times during a given interval---e.g., stocks that were among the top 20 most heavily traded for at least 80% of the trading days during the last quarter of 2017. We present a comprehensive suite of techniques for solving this problem, ranging from exact algorithms where k is fixed in advance, to approximate methods that work for any k and are able to exploit workload and data characteristics to improve accuracy while capping index cost. We show that our methods vastly outperform baseline and previous methods using both real and synthetic datasets.

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O (min n , √ rn )-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O (√ n )-approximation algorithm 1 .

We study a path-planning problem amid a set O of obstacles in R 2 , in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ε ∈ (0, 1]. Our algorithm computes in time O ( n 2 /ε 2 log n /ε) a path of total cost at most (1 + ε) times the cost of the optimal path.

Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric: * For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost. * For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point. * An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.

We consider the Approximate Nearest Neighbor (ANN) problem where the input set consists of n k-flats in the Euclidean Rd, for any fixed parameters k 0 is another prespecified parameter. We present an algorithm that achieves this task with n^{k+1}(log(n)/epsilon)^O(1) storage and preprocessing (where the constant of proportionality in the big-O notation depends on d), and can answer a query in O(polylog(n)) time (where the power of the logarithm depends on d and k). In particular, we need only near-quadratic storage to answer ANN queries amidst a set of n lines in any fixed-dimensional Euclidean space. As a by-product, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amidst k-flats with respect to any polyhedral distance function. Our results are more general, in that they also provide a tradeoff between storage and query time.

Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for maintaining the Reeb graph R of h as the heights of M's vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((k + g) n \polylog n) events; n is the number of vertices in M, and k is the number of external events which change the combinatorial structure of R. Each event is processed in O(\log^2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well.

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper we study the flooding query problem: Given a rain region R and a query point q on the terrain, quickly determine how much rain has to fall in R so that q is flooded. Available terrain data is often subject to uncertainty which must be incorporated into the terrain analysis. For instance, the digital elevation models of terrains have to be refined to incorporate underground pipes, tunnels, and waterways under bridges, but there is often uncertainty in their existence. By representing the uncertainty in the terrain data explicitly, we can develop methods for flood risk analysis that properly incorporate terrain uncertainty when reporting what areas are at risk of flooding.

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.

In many applications, the system needs to selectively present a small subset of answers to users. The set of all possible answers can be seen as an elevation surface over a domain, where the elevation measures the quality of each answer, and the dimensions of the domain correspond to attributes of the answers with which similarity between answers can be measured. This paper considers the problem of finding a diverse set of k high-quality representatives for such a surface. We show that existing methods for diversified top- k and weighted clustering problems are inadequate for this problem. We propose k -DHR as a better formulation for the problem. We show that k -DHR has a submodular and monotone objective function, and we develop efficient algorithms for solving k -DHR with provable guarantees. We conduct extensive experiments to demonstrate the usefulness of the results produced by k -DHR for applications in computational lead-finding and fact-checking, as well as the efficiency and effectiveness of our algorithms.

Our media is saturated with claims of “facts” made from data. Database research has in the past focused on how to answer queries, but has not devoted much attention to discerning more subtle qualities of the resulting claims, for example, is a claim “cherry-picking”? This article proposes a framework that models claims based on structured data as parameterized queries. Intuitively, with its choice of the parameter setting, a claim presents a particular (and potentially biased) view of the underlying data. A key insight is that we can learn a lot about a claim by “perturbing” its parameters and seeing how its conclusion changes. For example, a claim is not robust if small perturbations to its parameters can change its conclusions significantly. This framework allows us to formulate practical fact-checking tasks—reverse-engineering vague claims, and countering questionable claims—as computational problems. Along with the modeling framework, we develop an algorithmic framework that enables efficient instantiations of “meta” algorithms by supplying appropriate algorithmic building blocks. We present real-world examples and experiments that demonstrate the power of our model, efficiency of our algorithms, and usefulness of their results.

We present the first subquadratic algorithms for computing similarity between a pair of point sequences in R^d, for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + eps)-approximations of DTW and ED in near-linear time for point sequences drawn from k-packed or k-bounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is k-packed if the length of its intersection with any ball of radius r is at most kr, and it is k-bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1. The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimum-weight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimum-weight paths through these rectangles.

We propose parallel algorithms in the massively parallel communication (MPC) model (e.g. MapReduce) for processing large terrain elevation data (represented as a 3D point cloud) that are too big to fit on one machine. In particular, given a set S of 3D points that is distributed across multiple machines, we present a simple randomized algorithm to construct a TIN DEM of S by computing the Delaunay triangulation of the xy-projections of points in S, which is also stored across multiple machines. With high probability, the algorithm works in O(1) rounds and the total work performed is O(n log n). Next, we describe an efficient algorithm in the MPC model for computing the contour tree of the resulting DEM. Under some assumptions on the input, the algorithm works in O(1) rounds and the total work performed is O(n log n).

Dynamic time warping (DTW) is a widely used curve similarity measure. We present a simple and efficient (1 + ε)- approximation algorithm for DTW between a pair of point sequences, say, P and Q, each of which is sampled from a curve. We prove that the running time of the algorithm is O([EQUATION]n log σ) for a pair of k-packed curves with a total of n points, assuming that the spreads of P and Q are bounded by σ. The spread of a point set is the ratio of the maximum to the minimum pairwise distance, and a curve is called K- packed if the length of its intersection with any disk of radius r is at most Kr. Although an algorithm with similar asymptotic time complexity was presented in [1], our algorithm is considerably simpler and more efficient in practice.

We develop continuous-time probabilistic models to study trajectory data consisting of times and locations of user “check-ins”. We model the data as realizations of a marked point process, with intensity and mark-distribution modulated by a latent Markov jump process (MJP). We also include user-heterogeneity in our model by assigning each user a vector of “preferred locations”. Our model extends latent Dirichlet allocation by dropping the bag-of-words assumption and operating in continuous time. We show how an appropriate choice of priors allows efficient posterior inference. Our experiments demonstrate the usefulness of our approach by comparing with various baselines on a variety of tasks.

Motivated by the increasing popularity of electric vehicles (EV) and a lack of charging stations in the road network, we study the shortest path hitting set (SPHS) problem. Roughly speaking, given an input graph G, the goal is to compute a small-size subset H of vertices of G such that by placing charging stations at vertices in H, every shortest path in G becomes EV-feasible, i.e., an EV can travel between any two vertices of G through the shortest path with a full charge. In this paper, we propose a bi-criteria approximation algorithm with running time near-linear in the size of G that has a logarithmic approximation on |H| and may require the EV to slightly deviate from the shortest path. We also present a data structure for computing an EV-feasible path between two query vertices of G.

With the massive amounts of data available today, it is common to store and process data using multiple machines. Parallel programming platforms such as MapReduce and its variants are popular frameworks for handling such large data. We present the first provably efficient algorithms to compute, store, and query data structures for range queries and approximate nearest neighbor queries in a popular parallel computing abstraction that captures the salient features of MapReduce and other massively parallel communication (MPC) models. In particular, we describe algorithms for $kd$-trees, range trees, and BBD-trees that only require O(1) rounds of communication for both preprocessing and querying while staying competitive in terms of running time and workload to their classical counterparts. Our algorithms are randomized, but they can be made deterministic at some increase in their running time and workload while keeping the number of rounds of communication to be constant.

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.

We study a path-planning problem amid a set ℴ of obstacles in ℝ2, in which we wish to compute a short path between two points while also maintaining a high clearance from ℴ; the clearance of a point is its distance from a nearest obstacle in ℴ. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ∊ ∊ (0, 1]. Our algorithm computes in time a path of total cost at most (1 + ∊) times the cost of the optimal path.

Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has a wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability and (ii) estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.

Given a set of objects$\mathcal {O}$, each with$d$numeric attributes, atop-$k$preferencescores these objects using a linear combination of their attribute values, where the weight on each attribute reflects the interest in this attribute. Given a query preference$q$, atop-$k$queryfinds the$k$objects in$\mathcal {O}$with highest scores with respect to$q$. Given a query object$o$and a set of preferences$\mathcal {Q}$, areverse top-$k$queryfinds all preferences$q\in \mathcal {Q}$for which$o$becomes one of the top$k$objects with respect to$q$. Previous solutions to these problems are effective only in low dimensions. In this paper, we develop a solution for much higher dimensions (up to high tens), if many preferences exhibitsparsity—i.e., each specifies non-zero weights for only a handful (say$5$-$7$) of attributes (though the subsets of such attributes and their weights can vary greatly). Our idea is to select carefully a set of low-dimensionalcore subspacesto “cover” the sparse preferences in a workload. These subspaces allow us to index them more effectively than the full-dimensional space. Being multi-dimensional, each subspace covers many possible preferences; furthermore, multiple subspaces can jointly cover a preference, thereby expanding the coverage beyond each subspace’s dimensionality. Experimental evaluation validates our solution’s effectiveness and advantages over previous solutions.

We study the problem of maintaining the contour tree T of a terrain Sigma, represented as a triangulated xy-monotone surface, as the heights of its vertices vary continuously with time. We characterize the combinatorial changes in T and how they relate to topological changes in Sigma. We present a kinetic data structure (KDS) for maintaining T efficiently. It maintains certificates that fail, i.e., an event occurs, only when the heights of two adjacent vertices become equal or two saddle vertices appear on the same contour. Assuming that the heights of two vertices of Sigma become equal only O(1) times and these instances can be computed in O(1) time, the KDS processes O(kappa + n) events, where n is the number of vertices in Sigma and kappa is the number of events at which the combinatorial structure of T changes, and processes each event in O(log n) time. The KDS can be extended to maintain an augmented contour tree and a join/split tree.

We study contour trees of terrains, which encode the topological changes of the level set of the height value ℓ as we raise ℓ from -∞ to +∞ on the terrains, in the presence of uncertainty in data. We assume that the terrain is represented by a piecewise-linear height function over a planar triangulation M, by specifying the height of each vertex. We study the case when M is fixed and the uncertainty lies in the height of each vertex in the triangulation, which is described by a probability distribution. We present efficient sampling-based Monte Carlo methods for estimating, with high probability, (i) the probability that two points lie on the same edge of the contour tree, within additive error; (ii) the expected distance of two points p, q and the probability that the distance of p, q is at least ℓ on the contour tree, within additive error, where the distance of p, q on a contour tree is defined to be the difference between the maximum height and the minimum height on the unique path from p to q on the contour tree. The main technical contribution of the paper is to prove that a small number of samples are sufficient to estimate these quantities. We present two applications of these algorithms, and also some experimental results to demonstrate the effectiveness of our approach.

Given a finite range space Σ = (X, R), with N = |X| + |R|, we present two simple algorithms, based on the multiplicative-weight method, for computing a small-size hitting set or set cover of Σ. The first algorithm is a simpler variant of the Brönnimann-Goodrich algorithm but more efficient to implement, and the second algorithm can be viewed as solving a two-player zero-sum game. These algorithms, in conjunction with some standard geometric data structures, lead to near-linear algorithms for computing a small-size hitting set or set cover for a number of geometric range spaces. For example, they lead to O(N polylog(N)) expected-time randomized O(1)-approximation algorithms for both hitting set and set cover if X is a set of points and ℜ a set of disks in R2.

Computing paths over a terrain that are highly occluded with respect to observers is an important problem in GIS. Given a fast algorithm for computing the visibility map, the path-planning step becomes the bottleneck. In this paper, we present an approach for quickly computing occluded paths over a terrain using a sparse network, a sparse 1-dimensional network over the terrain. We present different strategies for constructing the sparse network. Experimental results show that our approach results in significantly improved time for computing highly occluded paths between two query points, and that the different strategies offer a tradeoff between higher-quality paths and lower preprocessing times. Furthermore, there are strategies that achieve near-optimal paths with small preprocessing cost.

Given a set of objects O, each with d numeric attributes, a top-k preference scores these objects using a linear combination of their attribute values, where the weight on each attribute reflects the interest in this attribute. Given a query preference q, a top-k query finds the k objects in O with highest scores with respect to q. Given a query object o and a set of preferences Q, a reverse top-k query finds all preferences q ∈ Q for which o becomes one of the top k objects with respect to q. Previous solutions to these problems are effective only in low dimensions. In this paper, we develop a solution for much higher dimensions (up to high tens), if many preferences exhibit sparsity-i.e., each specifies non-zero weights for only a handful (say 5-7) of attributes (though the subsets of such attributes and their weights can vary greatly). Our idea is to select carefully a set of low-dimensional core subspaces to “cover” the sparse preferences in a workload. These subspaces allow us to index them more effectively than the full-dimensional space. Being multi-dimensional, each subspace covers many possible preferences; furthermore, multiple subspaces can jointly cover a preference, thereby expanding the coverage beyond each subspace's dimensionality. Experimental evaluation validates our solution's effectiveness and advantages over previous solutions.

Are you fed up with "lies, d---ned lies, and statistics" made up from data in our media? For claims based on structured data, we present a system to automatically assess the quality of claims (beyond their correctness) and counter misleading claims that cherry-pick data to advance their conclusions. The key insight is to model such claims as parameterized queries and consider how parameter perturbations affect their results. We demonstrate our system on claims drawn from U.S. congressional voting records, sports statistics, and publication records of database researchers.

Let G = G(A∪B,A×B), with |A| = |B| = n, be a weighted bipartite graph, and let d(·,·) be the cost function on the edges. Let w(M) denote the weight of a matching in G, and M* a minimum-cost perfect matching in G. We call a perfect matching M c-approximate, for c ≥ 1, if w(M) ≤ c · w(M*). We present three approximation algorithms for computing minimum-cost perfect matchings in G.

Our news are saturated with claims of "facts" made from data. Database research has in the past focused on how to answer queries, but has not devoted much attention to discerning more subtle qualities of the resulting claims, e.g., is a claim "cherry-picking"? This paper proposes a framework that models claims based on structured data as parameterized queries. A key insight is that we can learn a lot about a claim by perturbing its parameters and seeing how its conclusion changes. This framework lets us formulate practical fact-checking tasks---reverse-engineering (often intentionally) vague claims, and countering questionable claims---as computational problems. Along with the modeling framework, we develop an algorithmic framework that enables efficient instantiations of "meta" algorithms by supplying appropriate algorithmic building blocks. We present real-world examples and experiments that demonstrate the power of our model, efficiency of our algorithms, and usefulness of their results.

The Fréchet distance measures similarity between two curves $f$ and $g$ that takes into account the ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along $f$, and its owner, walking along $g$, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on $m$ and $n$ specific stones, respectively. The stones are in fact sequences of points, typically sampled from the respective curves $f$ and $g$. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops from the starting points to the terminal points of their sequences. The discrete Fréchet distance can be computed in $O(mn)$ time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming $m\le n$, the algorithm runs in $O(\frac{mn\log\log n}{\log n})$ time, in the word RAM model, using $O(n)$ storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

Let C=C1,...,Cn} be a set of n pairwise-disjoint convex s-gons, for some constant s, and let p be a probability density function (pdf) over the non-negative reals. For each i, let Ki be the Minkowski sum of Ci with a disk of radius ri, where each ri is a random non-negative number drawn independently from the distribution determined by π. We show that the expected complexity of the union of K1,..,Kn is O(n log n), for any pdf p; the constant of proportionality depends on s, but not on the pdf. Next, we consider the following problem that arises in analyzing the vulnerability of a network under a physical attack. Let G=(V,E) be a planar geometric graph where E is a set of n line segments with pairwise-disjoint relative interiors. Let f: R -> [0,1] be an edge failure probability function, where a physical attack at a location x causes an edge e of E at distance r from x to fail with probability f(r); we assume that f is of the form f(x)=1-P(x), where P is a cumulative distribution function on the non-negative reals. The goal is to compute the most vulnerable location for G, i.e., the location of the attack that maximizes the expected number of failing edges of G. Using our bound on the complexity of the union of random Minkowski sums, we present a near-linear Monte-Carlo algorithm for computing a location that is an approximately most vulnerable location of attack for G.

Understanding the locations of highly occluded paths on a terrain is an important GIS problem. In this paper we present a model and a fast algorithm for computing highly occluded paths on a terrain. It does not assume the observer locations to be known and yields a path likely to be occluded under a rational observer strategy. We present experimental results that examine several different observer strategies. The repeated visibility map computations necessary for our model is expedited using a fast algorithm for calculating approximate visibility maps that models the decrease in observational fidelity as distance increases. The algorithm computes a multiresolution approximate visibility map and makes use of a graphics processing unit (GPU) to speed up computation. We present experimental results on terrrain data sets with up to 144 million points.

A fundamental problem in analyzing trajectory data is to identify common patterns between pairs or among groups of trajectories. In this paper, we consider the problem of matching similar portions between a pair of trajectories, each observed as a sequence of points sampled from it. We present new measures of trajectory similarity --- both local and global --- between a pair of trajectories to distinguish between similar and dissimilar portions. We then use this model to perform segmentation of a set of trajectories into fragments, contiguous portions of trajectories shared by many of them.

We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction-the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.

Nearest-neighbor (NN) search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability; (ii) estimating, within a specified additive error, the probability of a point being the nearest neighbor of a query point; (iii) using it to return the point that maximizes the probability being the nearest neighbor, or all the points with probabilities greater than some threshold to be the NN. We also present some experimental results to demonstrate the effectiveness of our approach.

The Fréchet distance is a similarity measure between two curves A and B that takes into account the location and ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along A, and its owner, walking along B, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on n and m specific stones on the curves A and B, respectively. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops. It can be computed in quadratic time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming m ≤ n, the algorithm runs in time, in the standard RAM model, using O(n) storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions---polyhedral terrains---can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in $O(n^{4/3}\operatorname{polylog}n)$ expected time, where $n$ is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a $(1+\varepsilon)$-approximation algorithm that runs in $O(n (1 + \log^2 (1/\varepsilon)))$ expected time for any fixed $\varepsilon >0$. The $(1+\varepsilon)$-approximation algorithm for bivariate functions runs in $O(n/\varepsilon)$ time, for any fixed $\varepsilon >0$, provided the two functions are defined over the same triangulation of their domain.

In this paper we show that dimensionality reduction (i.e., Johnson--Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally between low-dimensional flats, polynomial curves, curves with low winding degree, and polynomial surfaces. We also show that surfaces with bounded doubling dimension can be embedded into low dimension with small additive error. Finally, we show that for points with polynomial motion, the radius of the smallest enclosing ball can be preserved under dimensionality reduction.

Let $P$ be a set of $n$ points in $\mathbb{R}^d$. We present a linear-size data structure for answering range queries on $P$ with constant-complexity semialgebraic sets as ranges, in time close to $O(n^{1-1/d})$. It essentially matches the performance of similar structures for simplex range searching, and, for $d\ge 5$, significantly improves earlier solutions by the first two authors obtained in 1994. This almost settles a long-standing open problem in range searching. The data structure is based on a partitioning technique of Guth and Katz [On the Erdös distinct distances problem in the plane, arXiv:1011.4105, 2010], which shows that for a parameter $r$, $1 < r \le n$, there exists a $d$-variate polynomial $f$ of degree $O(r^{1/d})$ such that each connected component of $\mathbb{R}^d\setminus Z(f)$ contains at most $n/r$ points of $P$, where $Z(f)$ is the zero set of $f$. We present an efficient randomized algorithm for computing such a polynomial partition, which is of independent interest and is likely to have additional applications.

We study the mergeability of data summaries. Informally speaking, mergeability requires that, given two summaries on two datasets, there is a way to merge the two summaries into a single summary on the two datasets combined together, while preserving the error and size guarantees. This property means that the summaries can be merged in a way akin to other algebraic operators such as sum and max, which is especially useful for computing summaries on massive distributed data. Several data summaries are trivially mergeable by construction, most notably all the sketches that are linear functions of the datasets. But some other fundamental ones, like those for heavy hitters and quantiles, are not (known to be) mergeable. In this article, we demonstrate that these summaries are indeed mergeable or can be made mergeable after appropriate modifications. Specifically, we show that for ε-approximate heavy hitters, there is a deterministic mergeable summary of size O (1/ε); for ε-approximate quantiles, there is a deterministic summary of size O ((1/ε) log(ε n )) that has a restricted form of mergeability, and a randomized one of size O ((1/ε) log 3/2 (1/ε)) with full mergeability. We also extend our results to geometric summaries such as ε-approximations which permit approximate multidimensional range counting queries. While most of the results in this article are theoretical in nature, some of the algorithms are actually very simple and even perform better than the previously best known algorithms, which we demonstrate through experiments in a simulated sensor network. We also achieve two results of independent interest: (1) we provide the best known randomized streaming bound for ε-approximate quantiles that depends only on ε, of size O ((1/ε) log 3/2 (1/ε)), and (2) we demonstrate that the MG and the SpaceSaving summaries for heavy hitters are isomorphic.

Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures in their physical infrastructure, resulting from physical attacks (such as an electromagnetic pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network, but their effects cannot be determined exactly in advance. Therefore, we provide a unified framework to model network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, when network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows to identify locations that require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.

Let $P$ be a set of $n$ points in $\R^d$. We present a linear-size data structure for answering range queries on $P$ with constant-complexity semi algebraic sets as ranges, in time close to $O(n^{1-1/d})$. It essentially matches the performance of similar structures for simplex range searching, and, for $d\ge 5$, significantly improves earlier solutions by the first two authors obtained in~1994. This almost settles a long-standing open problem in range searching. The data structure is based on the polynomial-partitioning technique of Guth and Katz [arXiv:1011.4105], which shows that for a parameter $r$, $1

We consider how to support a large number of users over a wide-area network whose interests are characterised by range top-k continuous queries. Given an object update, we need to notify users whose top-k results are affected. Simple solutions include using a content-driven network to notify all users whose interest ranges contain the update (ignoring top-k), or using a server to compute only the affected queries and notifying them individually. The former solution generates too much network traffic, while the latter overwhelms the server. We present a geometric framework for the problem that allows us to describe the set of affected queries succinctly with messages that can be efficiently disseminated using content-driven networks. We give fast algorithms to reformulate each update into a set of messages whose number is provably optimal, with or without knowing all user interests. We also present extensions to our solution, including an approximate algorithm that trades off between the cost of server-side reformulation and that of user-side post-processing, as well as efficient techniques for batch updates.

Objects with multiple numeric attributes can be compared within any "subspace" (subset of attributes). In applications such as computational journalism, users are interested in claims of the form: Karl Malone is one of the only two players in NBA history with at least 25,000 points, 12,000 rebounds, and 5,000 assists in one's career. One challenge in identifying such "one-of-the-k" claims (k = 2 above) is ensuring their "interestingness". A small k is not a good indicator for interestingness, as one can often make such claims for many objects by increasing the dimensionality of the subspace considered. We propose a uniqueness-based interestingness measure for one-of-the-few claims that is intuitive for non-technical users, and we design algorithms for finding all interesting claims (across all subspaces) from a dataset. Sometimes, users are interested primarily in the objects appearing in these claims. Building on our notion of interesting claims, we propose a scheme for ranking objects and an algorithm for computing the top-ranked objects. Using real-world datasets, we evaluate the efficiency of our algorithms as well as the advantage of our object-ranking scheme over popular methods such as Kemeny optimal rank aggregation and weighted-sum ranking.

We study the mergeability of data summaries. Informally speaking, mergeability requires that, given two summaries on two data sets, there is a way to merge the two summaries into a single summary on the union of the two data sets, while preserving the error and size guarantees. This property means that the summaries can be merged in a way like other algebraic operators such as sum and max, which is especially useful for computing summaries on massive distributed data. Several data summaries are trivially mergeable by construction, most notably all the sketches that are linear functions of the data sets. But some other fundamental ones like those for heavy hitters and quantiles, are not (known to be) mergeable. In this paper, we demonstrate that these summaries are indeed mergeable or can be made mergeable after appropriate modifications. Specifically, we show that for ε-approximate heavy hitters, there is a deterministic mergeable summary of size O(1/ε) for ε-approximate quantiles, there is a deterministic summary of size O(1 over ε log(εn))that has a restricted form of mergeability, and a randomized one of size O(1 over ε log 3/21 over ε) with full mergeability. We also extend our results to geometric summaries such as ε-approximations and εkernels.

Nearest-neighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, such as sensor databases, location based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an ε-approximate ENN, for a given error parameter 0 < ε 0 < 1, under different distance functions. These methods build an index of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or ε-approximate ENN queries with provable performance guarantees.

Given a set of objects, each with multiple numeric attributes, a (preference) top-k query retrieves the k objects with the highest scores according to a user preference, defined as a linear combination of attribute values. We consider the problem of processing a large number of continuous top-k queries, each with its own preference. When objects or user preferences change, the query results must be updated. We present a dynamic index that supports the reverse top k query, which is of independent interest. Combining this index with another one for top-k queries, we develop a scalable solution for processing many continuous top-k queries that exploits the clusteredness in user preferences. We also define an approximate version of the problem and present a solution significantly more efficient than the exact one with little loss in accuracy.

For A, B ⊂ ℝd, |A| + |B| = n, let a ∊ A have a demand da ∊ ℤ+ and b ∊ B have a supply sb ∊ ℤ+, σa ∊ A da = σb ∊ B sb = U and let d(·, ·) be a distance function. Suppose the diameter of A ∪ B is Δ under d(·, ·), and ε > 0 is a parameter. We present an algorithm that in O((n√U log2 n + U log U) Φ (n) log(ΔU/ε)) time computes a solution to the transportation problem on A, B which is within an additive error ε from the optimal solution. Here Φ(n) is the query and update time of a dynamic weighted nearest neighbor data structure under distance function d(·, ·). Note that the (1/ε) appears only in the log term. As among various consequences we obtain, For A, B ⊂ ℝd and for the case where d(·, ·) is a metric, an ε-approximation algorithm for the transportation problem in O((n √log2 n + U log U) Φ(n) log (U/ε)) time. For A, B ⊂ [Δ]d and the L1 and L∞ distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O(n3/2 logd + Q(1) n log Δ) time. For A, B ⊂ [Δ]2 and RMS distance, exact algorithm for computing an optimal bipartite matching of A, B that runs in O(n3/2 + δ log Δ) time, for an arbitrarily small constant δ > 0. For point sets, A, B ⊂ [Δ], for the Lp norm and for 0 < α, β < 1, we present a randomized dynamic data structure that maintains a partial solution to the transportation problem under insertions and deletions of points in which at least (1 − α)U of the demands are satisfied and whose cost is within (1 + β) of that of the optimal (complete) solution to the transportation problem with high probability. The insertion, deletion and update times are O(poly(log(nΔ)/αβ)), provided U = nO(1).

For point sets A,B ⊂ Rd, |A|=|B|=n, and for a parameter ε > 0, we present an algorithm that computes, in O(n poly(log n, 1/ε)) time, an ε-approximate perfect matching of A and B with high probability; the previously best known algorithm takes Ω(n3/2) time. We approximate the Lp-norm using a distance function, d(•,•) based on a randomly shifted quad-tree. The algorithm iteratively generates an approximate minimum-cost augmenting path under d(•,•) in time proportional to the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O((n/ε)log n), implying that the running time of our algorithm is O(n poly(log n,1/ε)).

Let S be a set of n intervals in $\mathbb{R}$, and let $(\mathbf{S}, +)$ be any commutative semigroup. We assign a weight $\omega(s) \in \mathbf{S}$ to each interval in S. For a point $x \in \mathbb{R}$, let $S(x) \subseteq S$ be the set of intervals that contain x. Given a point $q \in \mathbb{R}$, the stabbing-semigroup query asks for computing $\sum_{s \in S(q)} \omega(s)$. We propose a linear-size dynamic data structure, under the pointer-machine model, that answers queries in worst-case $O(\log n)$ time and supports both insertions and deletions of intervals in amortized $O(\log n)$ time. It is the first data structure that attains the optimal $O(\log n)$ bound for all three operations. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in $O(\log_B n)$ I/Os, where B is the disk block size. For the restricted case of a nested family of intervals (either every pair of intervals is disjoint or one contains the other), we present a simpler solution based on dynamic trees.

Querying uncertain data has emerged as an important problem in data management due to the imprecise nature of many measurement data. In this article, we study answering range queries over uncertain data. Specifically, we are given a collection P of n uncertain points in ℝ, each represented by its one-dimensional probability density function (pdf). The goal is to build a data structure on P such that, given a query interval I and a probability threshold τ, we can quickly report all points of P that lie in I with probability at least τ. We present various structures with linear or near-linear space and (poly)logarithmic query time. Our structures support pdf's that are either histograms or more complex ones such as Gaussian or piecewise algebraic.

We study the problem of assigning subscribers to brokers in a wide-area content-based publish/subscribe system. A good assignment should consider both subscriber interests in the event space and subscriber locations in the network space, and balance multiple performance criteria including bandwidth, delay, and load balance. The resulting optimization problem is NP-complete, so systems have turned to heuristics and/or simpler algorithms that ignore some performance criteria. Evaluating these approaches has been challenging because optimal solutions remain elusive for realistic problem sizes. To enable proper evaluation, we develop a Monte Carlo approximation algorithm with good theoretical properties and robustness to workload variations. To make it computationally feasible, we combine the ideas of linear programming, randomized rounding, coreset, and iterative reweighted sampling. We demonstrate how to use this algorithm as a yardstick to evaluate other algorithms, and why it is better than other choices of yardsticks. With its help, we show that a simple greedy algorithm works well for a number of workloads, including one generated from publicly available statistics on Google Groups. We hope that our algorithms are not only useful in their own right, but our principled approach toward evaluation will also be useful in future evaluation of solutions to similar problems in content-based publish/subscribe.

Understanding the impact of climate and land-use on forest ecosystems involves modeling and simulating complex spatial interactions at many different scales. With this goal in mind, we have developed an individual-based, spatially explicit forest simulator, which incorporates fine-scale processes that influence forest dynamics. In this paper we present new, faster algorithms for computing understory light and for dispersal of seeds --- the two most computationally intensive submodules in our simulator. By exploiting temporal coherence, we circumvent the problem of doing the entire simulation at each step. We provide experimental results that support the efficiency and efficacy of our approach.

With modern focus on LiDAR technology the amount of topographic data, in the form of massive point clouds, has increased dramatically. Furthermore, due to the popularity of LiDAR, repeated surveys of the same areas are becoming more common. This trend will only increase as topographic changes prompt surveys over already scanned terrain, in which case we obtain large spatio-temporal data sets.

We study the problem of assigning subscribers to brokers in a wide-area content-based publish/subscribe system. A good assignment should consider both subscriber interests in the event space and subscriber locations in the network space, and balance multiple performance criteria including bandwidth, delay, and load balance. The resulting optimization problem is NP-complete, so systems have turned to heuristics and/or simpler algorithms that ignore some performance criteria. Evaluating these approaches has been challenging because optimal solutions remain elusive for realistic problem sizes. To enable proper evaluation, we develop a Monte Carlo approximation algorithm with good theoretical properties and robustness to workload variations. To make it computationally feasible, we combine the ideas of linear programming, randomized rounding, coreset, and iterative reweighted sampling. We demonstrate how to use this algorithm as a yardstick to evaluate other algorithms, and why it is better than other choices of yardsticks. With its help, we show that a simple greedy algorithm works well for a number of workloads, including one generated from publicly available statistics on Google Groups. We hope that our algorithms are not only useful in their own right, but our principled approach toward evaluation will also be useful in future evaluation of solutions to similar problems in content-based publish/subscribe.

Given a set of points with uncertain locations, we consider the problem of computing the probability of each point lying on the skyline, that is, the probability that it is not dominated by any other input point. If each point's uncertainty is described as a probability distribution over a discrete set of locations, we improve the best known exact solution. We also suggest why we believe our solution might be optimal. Next, we describe simple, near-linear time approximation algorithms for computing the probability of each point lying on the skyline. In addition, some of our methods can be adapted to construct data structures that can efficiently determine the probability of a query point lying on the skyline.

Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures of their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects are not deterministic. Therefore, we provide a unified framework to model the network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, in which network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, thereby demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows for identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.

A terrain M can be represented as a triangulation of the plane along with a height function associated with the vertices (and linearly interpolated within the edges and triangles) of M. We investigate the problem of answering contour queries on M: Given a height ℓ and a triangle f of M that intersects the level set of M at height ℓ, report the list of the edges of the connected component of this level set that intersect f, sorted in clockwise or counter-clockwise order. Contour queries are different from level-set queries in that only one contour (connected component of the level set) out of all those that may exist is expected to be reported. We present an I/O-efficient data structure of linear size that answers a contour query in O(logB N + T/B) I/Os, where N is the number of triangles in the terrain and T is the number of edges in the output contour. The data structure can be constructed using O(Sort(N)) I/Os.

Let C be a set of n axis-aligned cubes in ℜ3, and let U(C) denote the union of C. We present an algorithm that computes the volume of U(C) in time O(n polylog(n)). The previously best known algorithm takes O(n4/3 log2 n) time.

We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D - polyhedral terrains - can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4/3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1+ε)-approximation algorithm for minimizing the area that runs in O(n/√ε) time, for any fixed ε > 0. The (1 + ε)- approximation algorithm for the bivariate version, where volume is minimized, runs in O(n/ε2) time, for any fixed ε > 0, provided the two functions are defined over the same triangulation of their domain.

Let P be a set of n points in ℜ3. The 2-center problem for P is to find two congruent balls of the minimum radius whose union covers P. We present two randomized algorithms for computing a 2-center of P. The first algorithm runs in O(n3 log8 n) expected time, and the second algorithm runs in O(n2 log8 n/(1--r*/r0)3) expected time, where r* is the radius of the 2-center of P and r0 is the radius of the smallest enclosing ball of P. The second algorithm is faster than the first one as long as r* is not very close to r0, which is equivalent to the condition of the centers of the two balls in the 2-center of P not being very close to each other.

The best known upper bound on the number of topological changes in the Delaunay triangulation of a set of moving points in ℜ2 is (nearly) cubic, even if each point is moving with a fixed velocity. We introduce the notion of a stable Delaunay graph (SDG in short), a dynamic subgraph of the Delaunay triangulation, that is less volatile in the sense that it undergoes fewer topological changes and yet retains many useful properties of the full Delaunay triangulation. SDG is defined in terms of a parameter ± > 0, and consists of Delaunay edges pq for which the (equal) angles at which p and q see the corresponding Voronoi edge epq are at least ±. We prove several interesting properties of SDG and describe two kinetic data structures for maintaining it. Both structures use O*(n) storage. They process O*(n2) events during the motion, each in O*(1) time, provided that the points of P move along algebraic trajectories of bounded degree; the O*(·) notation hides multiplicative factors that are polynomial in 1/± and polylogarithmic in n. The first structure is simpler but the dependency on 1/± in its performance is higher.

With modern LiDAR technology the amount of topographic data, in the form of massive point clouds, has increased dramatically. One of the most fundamental GIS tasks is to construct a grid digital elevation model (DEM) from these 3D point clouds. In this paper we present a simple yet very fast algorithm for constructing a grid DEM from massive point clouds using natural neighbor interpolation (NNI). We use a graphics processing unit (GPU) to significantly speed up the computation. To handle the large data sets and to deal with graphics hardware limitations clever blocking schemes are used to partition the point cloud. For example, using standard desktop computers and graphics hardware, we construct a high-resolution grid with 150 million cells from two billion points in less than thirty-seven minutes. This is about one-tenth of the time required for the same computer to perform a standard linear interpolation, which produces a much less smooth surface.

Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g.\ in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as "Channel Discontinuity Constraint" (CDC). CDC-paths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an O(N2) distributed algorithm for discovering the shortest CDC-path between given source and destination. For use in wireless networks, we explain how spatial properties can be used for dramatically expedite the algorithm. This improves the running time of the O(N3) centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path. Our second result is a generalized t-spanner for CDC-path; For any ¿>0 we show how to construct a sub-network containing only O(N/¿) edges, such that that length of shortest CDC-paths between arbitrary sources and destinations increases by only a factor of at most 1/(1-2 sin (¿/2))2. This scheme can be implemented in a distributed manner with a message complexity of O(n log n) and it is highly dynamic, so addition/deletion of nodes are easily handled in a distributed manner. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone.

We develop (single-pass) streaming algorithms for maintaining extent measures of a stream S of n points in ℝd. We focus on designing streaming algorithms whose working space is polynomial in d (poly(d)) and sub-linear in n. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we introduce the notion of blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent of n.

In this article we present an I/O-efficient algorithm for the batched (off-line) version of the union-find problem. Given any sequence of N union and find operations, where each union operation joins two distinct sets, our algorithm uses O (SORT( N )) = O ( N / B log M/B N / B ) I/Os, where M is the memory size and B is the disk block size. This bound is asymptotically optimal in the worst case. If there are union operations that join a set with itself, our algorithm uses O (SORT( N ) + MST( N )) I/Os, where MST( N ) is the number of I/Os needed to compute the minimum spanning tree of a graph with N edges. We also describe a simple and practical O (SORT( N ) log( N / M ))-I/O algorithm for this problem, which we have implemented. We are interested in the union-find problem because of its applications in terrain analysis. A terrain can be abstracted as a height function defined over R 2 , and many problems that deal with such functions require a union-find data structure. With the emergence of modern mapping technologies, huge amount of elevation data is being generated that is too large to fit in memory, thus I/O-efficient algorithms are needed to process this data efficiently. In this article, we study two terrain-analysis problems that benefit from a union-find data structure: (i) computing topological persistence and (ii) constructing the contour tree. We give the first O (SORT( N ))-I/O algorithms for these two problems, assuming that the input terrain is represented as a triangular mesh with N vertices.

We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the article, we consider two sets A,B of balls in R d , d =2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t , the set of all balls in A shifted by t , and B . We consider several variants of this problem. First, we extend the notion of Hausdorff distance from sets of points to sets of balls, so that each ball has to be matched with the nearest ball in the other set. We also consider the problem in the standard setting, by computing the Hausdorff distance between the unions of the two sets (as point sets). Second, we consider either all possible translations t (as is the standard approach), or consider only translations that keep the balls of A+t disjoint from those of B . We propose several exact and approximation algorithms for these problems. In the second part of the article, we note that the Hausdorff distance is sensitive to outliers, and thus consider two variants that are more robust: the root-mean-square (rms) and the summed Hausdorff distance. We propose efficient approximation algorithms for computing the minimum rms and the minimum summed Hausdorff distances under translation, between two point sets in R d . In order to obtain a fast algorithm for the summed Hausdorff distance, we propose a deterministic efficient dynamic data structure for maintaining an ϵ-approximation of the 1-median of a set of points in R d , under insertions and deletions.

Given a set system (X,R), the hitting set problem is to find a smallest-cardinality subset H ⊆ X, with the property that each range R ∈ R has a non-empty intersection with H. We present near-linear time approximation algorithms for the hitting set problem, under the following geometric settings: (i) R is a set of planar regions with small union complexity. (ii) R is a set of axis-parallel d-rectangles in d-space. In both cases X is either the entire d-dimensional space or a finite set of points in d-space. The approximation factors yielded by the algorithm are small; they are either the same as or within an O(log n) factor of the best factors known to be computable in polynomial time.

Querying uncertain data has emerged as an important problem in data management due to the imprecise nature of many measurement data. In this paper we study answering range queries over uncertain data. Specifically, we are given a collection P of n points in R, each represented by its one-dimensional probability density function (pdf). The goal is to build an index on P such that given a query interval I and a probability threshold τ, we can quickly report all points of P that lie in I with probability at least τ. We present various indexing schemes with linear or near-linear space and logarithmic query time. Our schemes support pdf's that are either histograms or more complex ones such as Gaussian or piecewise algebraic. They also extend to the external memory model in which the goal is to minimize the number of disk accesses when querying the index.

We develop algorithms and data structures for the approximate Euclidean shortest path problem amid a set P of k convex obstacles in R 2 and R 3 , with a total of n faces.The running time of our algorithms is linear in n, and the size and query time of our data structure are independent of n.We follow a "core-set" based approach, i.e., we quickly compute a small sketch Q of P whose size is independent of n and then compute approximate shortest paths with respect to Q.

This article considers the problem of scalably processing a large number of continuous queries. Our approach, consisting of novel data structures and algorithms and a flexible processing framework, advances the state-of-the-art in several ways. First, our approach is query sensitive in the sense that it exploits potential overlaps in query predicates for efficient group processing. We partition the collection of continuous queries into groups based on the clustering patterns of the query predicates, and apply specialized processing strategies to heavily clustered groups (or hotspots ). We show how to maintain the hotspots efficiently, and use them to scalably process continuous select-join, band-join, and window-join queries. Second, our approach is also data sensitive, in the sense that it makes cost-based decisions on how to process each incoming tuple based on its characteristics. Experiments demonstrate that our approach can improve the processing throughput by orders of magnitude.

A terrain M is the graph of a bivariate function. We assume that M is represented as a triangulated surface with N vertices. A contour (or isoline) of M is a connected component of a level set of M. Generically, each contour is a closed polygonal curve; at "critical" levels these curves may touch each other or collapse to a point. We present I/O efficient algorithms for the following two problems related to computing contours of M:

The problem of maintaining a valid mesh (triangulation) within a certain domain that deforms over time arises in many applications. During a period for which the underlying mesh topology remains unchanged, the deformation moves vertices of the mesh and thus potentially turns a mesh invalid, or as we call it, tangled. We introduce the notion of locally removable regions, which are certain tangled regions in the mesh that allow for local removal and re-meshing. We present an algorithm that is able to quickly compute, through local explorations, a minimum locally removable region containing a "seed" tangled region in an invalid mesh. By re-meshing within this area, the "seed" tangled region can then be removed from the mesh without introducing any new tangled region. The algorithm is output-sensitive in the sense that it never explores outside the output region.

We demonstrate ProSem, a scalable wide-area publish/subscribe system that supports complex, stateful subscriptions as well as simple ones. One unique feature of ProSem is its cost-based joint optimization of both subscription processing and notification dissemination. ProSem uses novel reformulation techniques to expose new alternatives for processing and disseminating data using standard stateless content-driven network components.

We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving points in the plane; insertions and deletions of points are also allowed. If no insertions or deletions take place, the structure for the closest pair uses O ( n log n ) space, and processes O ( n 2 β s +2 ( n )log n ) critical events, each in O (log 2 n ) time. Here s is the maximum number of times where the distances between any two specific pairs of points can become equal, β s ( q ) = λ s ( q )/ q , and λ s ( q ) is the maximum length of Davenport-Schinzel sequences of order s on q symbols. The dynamic version of the problem incurs a slight degradation in performance: If m ≥ n insertions and deletions are performed, the structure still uses O ( n log n ) space, and processes O ( mn β s +2( n )log 3 n ) events, each in O (log 3 n ) time. Our kinetic data structure for all nearest neighbors uses O ( n log 2 n ) space, and processes O ( n 2 β 2 s +2 ( n )log 3 n ) critical events. The expected time to process all events is O ( n 2 β s +2 2 ( n ) log 4 n ), though processing a single event may take Θ( n ) expected time in the worst case. If m ≥ n insertions and deletions are performed, then the expected number of events is O ( mn β 2 s +2 ( n ) log 3 n ) and processing them all takes O ( mn β 2 s +2 ( n ) log 4 n ). An insertion or deletion takes O ( n ) expected time.

Given a set S of n points in R 3 , a point x in R 3 is called center point of S if every closed halfspace whose bounding hyperplane passes through x contains at least ⌈ n /4⌉ points from S . We present a near-quadratic algorithm for computing the center region , that is the set of all center points, of a set of n points in R 3 . This is nearly tight in the worst case since the center region can have Ω( n 2 ) complexity. We then consider sets S of 3 n points in the plane which are the union of three disjoint sets consisting respectively of n red, n blue, and n green points. A point x in R 2 is called a colored Tverberg point of S if there is a partition of S into n triples with one point of each color, so that x lies in all triangles spanned by these triples. We present a first polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such a 3-colored set S .

We consider the problem of bounding the maximum possible number fk,d(n) of k-simplices that are spanned by a set of n pointsin Rd and are similar to a given simplex. We first show that f2,3(n) = O(n13/6), and then tacklethe general case, and show that fd-2, d(n) = O(nd-8/5) and fd-1,d(n) = O*(nd-72/55), for any d.Our technique extends to derive bounds for other valuesof k and d, and we illustrate this by showing that f2,5(n)=O(n8/3).

In this paper we show that dimensionality reduction (i.e., Johnson-Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally between low-dimensional flats, polynomial curves, curves with low winding degree, and polynomial surfaces. We also show that surfaces with bounded doubling dimension can be embedded into low dimension with small additive error. Finally, we show that for points with polynomial motion, the radius of the smallest enclosing ball can be preserved under dimensionality reduction.

Let C be a set of n axis-aligned cubes in R3, and let U(C) denote the union of C. We present an algorithmthat can compute the volume of U(C) in time O(n4/3 log n). The previously best known algorithm, by Overmars and Yap, computes the volume of the union ofany n axis-aligned boxes in R3 in O(n3/2log n) time.

Given a point set P⊆R2, a subset Q⊆ P is an ε-kernel of P if for every slab W containing Q, the (1+ε)-expansion of W also contains P. We present a data-stream algorithm for maintaining an ε-kernel of a stream of points in R2 that uses O(1/√ ε) space and takes O(log (1/ε)) amortized time to process each point. This is the first space-optimal data-stream algorithm for this problem.

We consider the problem of extracting a river network and a watershed hierarchy from a terrain given as a set of irregularly spaced points. We describe TERRASTREAM, a "pipelined" solution that consists of four main stages: construction of a digital elevation model (DEM), hydrological conditioning, extraction of river networks, and construction of a watershed hierarchy. Our approach has several advantages over existing methods. First, we design and implement the pipeline so that each stage is scalable to massive data sets; a single non-scalable stage would create a bottleneck and limit overall scalability. Second, we develop the algorithms in a general framework so that they work for both TIN and grid DEMs. Furthermore, TERRASTREAM is flexible and allows users to choose from various models and parameters, yet our pipeline is designed to reduce (or eliminate) the need for manual intervention between stages.

We consider sensors, such as fibers, lasers, and pyroelectric motion detectors, that fire when objects cross a boundary. A moving object can be localized by analyzing sequences of boundary crossings. We consider the number of distinct sequences and object positions that can be achieved using boundary sensors in one- and two-dimensional spaces. For 1D systems we use representations of sensor sequences on graphs to derive limits on the number of object locations that can be monitored by a given sensor population and sequence length. For 2D systems we show that in certain circumstances the ratio of the number of unique sensor sequences to the number of unique object paths is exponential in the sequence length and we argue that the probability of unique identification is high for sufficiently large sequences. We also prove the triangle grid can track an object with error limited to a small neighborhood.

Despite extensive study over the last four decades and numerous applications, no I/O-efficient algorithm is known for the union-find problem. In this paper we present an I/O-efficient algorithm for the batched (off-line) version of the union-find problem. Given any sequence of N union and find operations, where each union operation joins two distinct sets, our algorithm uses O(sort(N)) = O(N/BlogM/BN/B) I/Os, where M is the memory size and B is the disk block size. This bound is asymptotically optimal in the worst case. If there are union operations that join a set with itself, our algorithm uses O(sort(N) + mst(N)) I/Os, where mst(N) is the number of I/Os needed to compute the minimum spanning tree of a graph with N edges. We also describe a simple and practical O(sort(N)log(N/M))-I/O algorithm for this problem, which we have implemented.We are interested in the union-find problem because of its applications in terrain analysis. A terrain can be abstracted as a height function defined over R2, and many problems that deal with such functions require a union-find data structure. With the emergence of modern mapping technologies, huge amount of elevation data is being generated that is too large to fit in memory, thus I/O-efficient algorithms are needed to process this data efficiently. In this paper, we study two terrain analysis problems that benefit from a union-find data structure: (i) computing topological persistence and (ii) constructing the contour tree. These structures have important applications such as terrain modeling, flow analysis, topological feature extraction, etc. We give the first O(sort(N))-I/O algorithms for these two problems, assuming that the input terrain is represented as a triangular mesh with N vertices.Finally, we report some preliminary experimental results, showing that our algorithms give order-of-magnitude improvement over previous methods on large data sets that do not fit in memory.

Let S be a set of n points in $\reals^2$. Given an integer $1 \le k \le n$, we wish to find a maximally separated subset $I \subseteq S$ of size k; this is a subset for which the minimum among the ${k\choose 2}$ pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists $I\subseteq S$, $|I|=k$, so that all ${k\choose 2}$ pairwise distances in I are at least 2. This problem can also be formulated in terms of disk‐intersection graphs: Let D be the set of unit disks centered at the points of S. The disk‐intersection graph G of D has as edges all pairs of disks with nonempty intersection. Any set I with the above properties is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NP‐complete if k is part of the input. In this paper we first present a linear‐time $\eps$‐approximation algorithm for any constant k. Next we give exact algorithms for the cases $k=3$ and $k=4$ that run in time $O(n^{4/3}\polylog(n))$. We also present a simpler $n^{O(\sqrt{k})}$‐time exact algorithm (as compared with the recent algorithm in [J. Alber and J. Fiala, J. Algorithms, 52 (2004), pp. 134–151]) for arbitrary values of k.

A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding whether two sets of n points in ℝ 3 can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double wedge. The latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.

Multiple Sequence Alignment (MSA) is one of the most fundamental problems in computational molecular biology. The running time of the best known scheme for finding an optimal alignment, based on dynamic programming, increases exponentially with the number of input sequences. Hence, many heuristics were suggested for the problem. We consider a version of the MSA problem where the goal is to find an optimal alignment in which matches are restricted to positions in predefined matching segments. We present several techniques for making the dynamic programming algorithm more efficient, while still finding an optimal solution under these restrictions. We prove that it suffices to find an optimal alignment of the predefined sequence segments, rather than single letters, thereby reducing the input size and thus improving the running time. We also identify "shortcuts" that expedite the dynamic programming scheme. Empirical study shows that, taken together, these observations lead to an improved running time over the basic dynamic programming algorithm by 4 to 12 orders of magnitude, while still obtaining an optimal solution. Under the additional assumption that matches between segments are transitive, we further improve the running time for finding the optimal solution by restricting the search space of the dynamic programming algorithm.

A model for segmentation of an object space by an array of binary, radiation-field sensors and geometric reference structures is described. Given a family of binary, radiation-field sensors and a geometric reference structure, we refer to the set of sensor states induced by a source at point p as the signature of p . We study the segmentation of an object space into signature cells and prove near optimal bounds on the number of distinct signatures induced by a point source, as a function of sensor and reference structure complexity. We also show that almost any family of signatures can be implemented under this model.

Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on T, and whose top endpoints guard T, in the sense that each point on T is visible from at least one of them. In this paper we present the following results for the two-watchtower problem in R2 and R3: (1) We show that the discrete two-watchtowers problem in R2, where the bases are constrained to lie at vertices of T, can be solved in O(n2 log4n) time, significantly improving previous solutions. The algorithm works, without increasing its asymptotic running time, even if, one of the towers is allowed to be placed anywhere on T. (2) We show that the continuous two-watchtower problem in R2, where the bases can lie anywhere on T, can be solved in O(n3α(n)log3n) time, again significantly improving previous results. (3) Still in R2, we show that the continuous version of the problem of guarding a finite set P ⊂ T of m points by two watchtowers of smallest height can be solved in O(mn log4n) time. (4) The discrete version of the two-watchtower problem in R3 can be solved in O(n11/3 polylog(n)) time; this is the first nontrivial result for this problem in R3.

A finite collection of x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each other there. Let L be such a collection of n pseudo-lines, and let P be a set of m points in $\reals^2$. Extending a result of Goodman [Discrete Math., 32 (1980), pp. 27--35], we define a duality transform that maps L to a set L* of points in $\reals^2$ and P to a set P* of (x-monotone) pseudo-lines in $\reals^2$, so that the incidence and the "above-below" relations between the points and the pseudo-lines are preserved. We present an efficient algorithm for computing the dual arrangement {\eus A}$(P^*)$ under an appropriate model of computation. We also present a dynamic data structure for reporting, in $O(m^\eps + k)$ time, all k points of P that lie below a query arc, which is either a circular arc or a portion of the graph of a polynomial of fixed degree. This result is needed for computing the dual arrangement for certain classes of pseudo-lines arising in several applications, but is also interesting in its own right. We present a few applications of our dual arrangement algorithm, such as computing incidences between points and pseudo-lines and computing a subset of faces in a pseudo-line arrangement. Next, we present an efficient algorithm for cutting a set of circles into arcs so that every pair of arcs intersect in at most one point, i.e., the resulting arcs constitute a collection of pseudo-segments. By combining this algorithm with our algorithm for computing the dual arrangement of pseudo-lines, we obtain efficient algorithms for several problems involving arrangements of circles or circular arcs, such as reporting or counting incidences between points and circles and computing a set of marked faces in arrangements of circles.

Let B be a set of n unit balls in ℝ3. We show that the combinatorial complexity of the space of lines in ℝ3 that avoid all the balls of B is O(n 3+e), for any ε0. This result has connections toproblems in visibility, ray shooting, motion planning andgeometric optimization.

Given a smoothly embedded 2-manifold in ℝ3, we define the elevation of a point as the height difference to a canonically defined second point on the same manifold. Our definition is invariant under rigid motions and can be used to define features such as lines of discontinuous or continuous but non-smooth elevation. We give an algorithm for finding points of locally maximum elevation, which we suggest mark cavities and protrusions and are useful in matching shapes as for example in protein docking.

We present a near-quadratic algorithm for computing the center regionof a set of n points in three dimensions. This is nearly tight inthe worst case since the center region can have Ω(n2) complexity. We then consider the problem of recognizing whether a given point q is a colored Tverberg point of a set of n colored points in the plane, and present the first polynomial-time algorithm for this problem.

In the Euclidean bipartite matching problem, we are given a set R of "red" points and a set B of "blue" points in ℝ3 where |R| = |B| = n, and we want to pair up each red point with a distinct blue point so that the sum of distances between the paired points is minimized. We present an approximation algorithm that given any parameter 0 < ε < 1 runs in O(n1+ε) expected time and returns a matching whose expected cost is within a multiplicative factor O(log (1/ε)) of the optimal. The dimension d is considered to be a fixed constant.

A triangulation of a set S of points in the plane is a subdivision of the convex hull of S into triangles whose vertices are points of S. Given a set S of n points in ℝ3, each moving independently, we wish to maintain a triangulation of S. The triangulation needs to be updated periodically as the points in S move, so the goal is to maintain a triangulation with small number of topological events, each being the insertion or deletion of an edge. We propose a kinetic data structure (KDS) that processes n2 2O(√log n•log log n ) topological events, with high probability, if the trajectories of input points are algebraic curves of fixed degree. Each topological event can be processed in O(log n) time. This is the first known KDS for maintaining a triangulation that processes near-quadratic number of topological events, and almost matches the Ω(n2) lower bound, [1]. The number of topological events can be reduced to nk • 2O(√log k•log log n ) if only K of the points are moving.

Models of forest ecosystems are needed to understand how climate and land-use change can impact biodiversity. In this paper we describe an individual-based, spatially-explicit forest simulator with full accounting of both landscape context and the fine-scale processes that influence forest dynamics. Unfortunately, performing realistic forest simulations of such models is computationally infeasible. We design efficient algorithms for computing seed dispersal and light, using a plethora of techniques. These include hierarchical spatial decomposition, monopole approximation and utilizing the graphics hardware for fast geometric computations. These algorithms allow us to simulate large landscapes for long periods of time.

The notion of ε-kernel was introduced by Agarwal et al. to set up a unified framework for computing various extent measures of a point set p approximately. Roughly speaking, a subset Q ⊆ P is an ε-kernel of P if for every slab W containing Q, the expanded slab (1+ε)W contains P. They illustrated the significance of an ε-kernel by showing that it yields approximation algorithms for a wide range of problems.We present a simpler and more practical algorithm for computing the ε-kernel of a set P of points in ℝ3. We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε-kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus. Finally, we show that ε-kernels can be effectively used to expedite the algorithms for maintaining extents of moving points.

In many applications it is desirable to cluster high dimensional data along various subspaces, which we refer to as projective clustering. We propose a new objective function for projective clustering, taking into account the inherent trade-off between the dimension of a subspace and the induced clustering error. We then present an extension of the k-means clustering algorithm for projective clustering in arbitrary subspaces, and also propose techniques to avoid local minima. Unlike previous algorithms, ours can choose the dimension of each cluster independently and automatically. Furthermore, experimental results show that our algorithm is significantly more accurate than the previous approaches.

We present a general technique for approximating various descriptors of the extent of a set P of n points in R d when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a parameter ε > 0, it computes in time O ( n + 1/ε O (1) ) a subset Q ⊆ P of size 1/ε O (1) , with the property that (1 − ε)μ( P ) ≤ μ( Q ) ≤ μ( P ). The specific applications of our technique include ε-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P , (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P . Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms.

A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if the closed Jordan region that it bounds does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. We use this bound to show that any collection of n x -monotone pseudo-circles can be cut into O ( n 8/5 ) arcs so that any two intersect at most once; this improves a previous bound of O ( n 5/3 ) due to Tamaki and Tokuyama. If, in addition, the given collection admits an algebraic representation by three real parameters that satisfies some simple conditions, then the number of cuts can be further reduced to O ( n 3/2 (log n ) O (α( s ( n )) ), where α( n ) is the inverse Ackermann function, and s is a constant that depends on the the representation of the pseudo-circles. For arbitrary collections of pseudo-circles, any two of which intersect exactly twice, the number of necessary cuts reduces still further to O ( n 4/3 ). As applications, we obtain improved bounds for the number of incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, of pairwise intersecting pseudo-circles, of arbitrary x -monotone pseudo-circles, of parabolas, and of homothetic copies of any fixed simply shaped convex curve. We also obtain a variant of the Gallai--Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound on the number of distinct distances under any well-behaved norm.

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in IRd lying in a query hyper-rectangle. Cache-oblivious data structures are designed to be efficient in arbitrary memory hierarchies.We describe a dynamic linear-size data structure that answers d-dimensional queries in O((N/B)1-1/d+T/B) memory transfers, where B is the block size of any two levels of a multilevel memory hierarchy. A point can be inserted into or deleted from this data structure in O(log2B N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logB N+T/B) memory transfers using O(N log22 N) space. The analysis of the latter structure requires that B=22c for some non-negative integer constant c.

We study the shape matching problem under the Hausdorff distance and its variants. Specifically, we consider two sets A,B of balls in Rd, d=2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t, the set of all balls in A shifted by t, and B. We consider several variants of this problem. First, we extend the notion of Hausdorff distance from sets of points to sets of balls, so that each ball has to be matched with the nearest ball in the other set. We also consider the problem in the standard setting, by computing the Hausdorff distance between the unions of the two sets (as point sets). Second, we consider either all possible translates t (as is the standard approach), or consider only translations that keep the balls of A+t disjoint from those of B. We propose several exact and approximation algorithms for these problems. Since the Hausdorff distance is sensitive to outliers, we also propose efficient approximation algorithms for computing the minimum root mean-square (rms) and the minimum summed Hausdorff distance, under translation, between two point sets in Rd. In order to obtain a fast algorithm for the summed Hausdorff distance, we propose a deterministic efficient dynamic data structure for maintaining an e-approximation of the 1-median of a set of points, under insertion and deletion.

We introduce a hierarchical variant of the probabilistic roadmap method for motion planning. By recursively refining an initially sparse sampling in neighborhoods of the obstacle boundary, our algorithm generates a smaller roadmap that is more likely to find narrow passages than uniform sampling. We analyze the failure probability and computation time, relating them to path length, path clearance, roadmap size, recursion depth, and a local property of the free space. The approach is general, and can be tailored to any variety of robots. In particular, we describe algorithmic details for a planar articulated arm.

We propose a mathematical formulation for the notion of optimal projective cluster, starting from natural requirements on the density of points in subspaces. This allows us to develop a Monte Carlo algorithm for iteratively computing projective clusters. We prove that the computed clusters are good with high probability. We implemented a modified version of the algorithm, using heuristics to speed up computation. Our extensive experiments show that our method is significantly more accurate than previous approaches. In particular, we use our techniques to build a classifier for detecting rotated human faces in cluttered images.

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.

A box-tree is a \ifasci so-called \emph{bounding-volume hierarchy} \else bounding-volume hierarchy \fi that uses axis-aligned boxes as bounding volumes. The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes visited when answering such a query. We describe several new algorithms for constructing box-trees with small worst-case query complexity with respect to queries with axis-parallel boxes and with points. We also prove lower bounds on the worst-case query complexity for box-trees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert box-trees to R-trees, resulting in R-trees with (almost) optimal query complexity.

We derive improved bounds on the number of k-dimensional simplices spa nned by a set of n points in $\reals^d$ that are congruent to a given $k$-simplex, for $k\le d-1$. Let $f_k^{(d)} (n)$ be the maximum number of $k$-simplices spanned by a set of $n$ points in $\reals^d$ that are congruent to a given $k$-simplex. We prove that $f_2^{(3)}(n) = O(n^{5/3}\cdot 2^{O(\alpha^2(n))})$, $f_2^{(4)} (n) = O(n^{2+\eps})$, $f_2^{(5)} (n) = \Theta(n^{7/3})$, and $f_3^{(4)} (n) = O(n^{9/4+\eps})$. We also derive a recurrence to bound $f_k^{(d)} (n)$ for arbitrary values of $k$ and $d$, and use it to derive the bound $f_k^{(d)} (n) = O(n^{d/2})$ for $d \le 7$ and $k \le d-2$. Following Erd{\H o}s and Purdy, we conjecture that this bound holds for larger values of $d$ as well, and for $k\le d-2$.

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for general circles, they nearly coincide with the best known bounds for the number of incidences between m points and n circles.

This paper addresses the issue of trap design for sensorless automated assembly. First, we present a simple algorithm that determines in O(nm /spl alpha/(nm) log(nm)) time whether an n-sided polygonal part will fall through an m-sided polygonal trap. We then introduce the notion of a minimal trap for a polygonal part, and develop an algorithm to design a family of minimal feeders built from these traps. The algorithm runs in O(kn/sup 3+/spl epsiv//) time, where k is the number of stable orientations of P. Moreover, it is complete in the sense that we can always find a feeder, provided that one exists that rejects and supports the appropriate poses of the part.

The algorithms for computing a shortest path on a polyhedral surface are slow, complicated, and numerically unstable.We have developed and implemented a robust and efficient algorithm for computing approximate shortest paths on a convex polyhedral surface.Given a convex polyhedral surface P in R 3 , two points s, t E P, and a parameter e > 0, it computes a path between s and t on P whose length is at most (1 + c) times the length of the shortest path between those points.It first constructs in time O(n/v~ ) a graph of size O(1/s4), computes a shortest path on this graph, and projects the path onto the surface in O(n/c) time, where n is the number of vertices of P. In the post-processing we have added a heuristic that considerably improves the quality of the resulting path.

We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle R and a real value tq, report all K points of S that lie inside R at time tq. We first present an indexing structure that, for any given constant ε > 0, uses O(N/B) disk blocks, where B is the block size, and answers a query in O((N/B)1/2+ε + K/B) I/Os. It can also report all the points of S that lie inside R during a given time interval. A point can be inserted or deleted, or the trajectory of a point can be changed, in O(log2B N) I/Os. Next, we present a general approach that improves the query time if the queries arrive in chronological order, by allowing the index to evolve over time. We obtain a trade off between the query time and the number of times the index needs to be updated as the points move. We also describe an indexing scheme in which the number of I/Os required to answer a query depends monotonically on the difference between tq and the current time. Finally, we develop an efficient indexing scheme to answer approximate nearest-neighbor queries among moving points.

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in ${\Bbb R}^3$ such that the aspect ratio of each rectangle in S is at most $\alpha$, for some constant $\alpha \geq 1$. We present an $n2^{O(\sqrt{\log n})}$-time algorithm to build a binary space partition of size $n2^{O(\sqrt{\log n})}$ for S. We also show that if m of the n rectangles in S have aspect ratios greater than $\alpha$, we can construct a BSP of size $n\sqrt{m}2^{O(\sqrt{\log n})}$ for S in $n\sqrt{m}2^{O(\sqrt{\log n})}$ time. The constants of proportionality in the big-oh terms are linear in $\log \alpha$. We extend these results to cases in which the input contains nonorthogonal or intersecting objects.

Let B be a point robot in the plane, whose path is constrained to have curvature of at most 1, and let $\Omega$ be a set of polygonal obstacles with n vertices. We study the collision-free, optimal path-planning problem for B. Given a parameter $\varepsilon$, we present an $O( (n^2/ \eps^4) \log n)$-time algorithm for computing a collision-free, curvature-constrained path between two given positions, whose length is at most $(1+\varepsilon)$ times the length of an optimal path, provided it is robust. (Roughly speaking, a path is robust if it remains collision-free even if certain positions on the path are perturbed). Our algorithm thus runs significantly faster than the previously best known algorithm by Jacobs and Canny whose running time is $O( (\frac{n+L}{\eps^2})^2 + n^2 (\frac{n+L}{\eps^2}) \log n)$, where L is the total edge length of the obstacles. More importantly, the running time of our algorithm does not depend on the size of obstacles. The path returned by this algorithm is not necessarily robust. We present an $O((n^{2.5}/ \eps^4) \log n)$-time algorithm that returns a robust path whose length is at most $(1+\varepsilon)$ times the length of an optimal path, provided it is robust. We also give a stronger characterization of curvature-constrained shortest paths, which, apart from being crucial for our algorithm, is interesting in its own right. Roughly speaking, we prove that, except in some special cases, a shortest path touches obstacles at points that have a visible vertex nearby.

We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in ${\mathbb R}^3$ and two points s and t on P, constructs a path on P between s and t whose length is at most ${7(1+{\varepsilon})} d P (s,t), where d P (s,t) is the length of the shortest path between s and t on P, and ${\varepsilon} > 0$ is an arbitrarily small positive constant. The algorithm runs in O(n 5/3 log 5/3 n ) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n 8/5 log 8/5 n ) time and returns a path whose length is at most ${15(1+{\varepsilon})} d_{P}(s,t)$.

Let S be a set of n points in R d . The "roundness" of S can be measured by computing the width ! = ! (S) of the thinnest spherical shell (or annulus in R 2 ) that contains S. This paper contains three main results related to computing ! : (i) For d = 2, we can compute in O(n log n) time an annulus containing S whose width is at most 2! (S). We extend this algorithm, so that for any given parameter " ? 0, an annulus containing S whose width is at most (1 + ")! , is computed in time O(n log n + n=" 2 ). (ii) For d 3, given a parameter " ? 0, we can compute a shell containing S of width at most (1+ ")! either in time O \\Gamma n " d log( \\Delta ! " ) \\Delta or in time O \\Gamma n " d\\Gamma2 \\Gamma log n + 1 " \\Delta log \\Gamma \\Delta ! " \\Delta\\Delta . Work by P.A. was supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants EIA--9870724, and CCR--9732787, by an NYI award, and by a grant from ...

IntroductionWe revisit the notion of kinetic efficiency for noncanonically-defined discrete attributes of moving data, like binary space partitions and triangulations.Under very general computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of moving segments in the plane or any Steiner triangulation of moving points in the plane.Such lower bounds-the first to be obtained in the kinetic context-are necessary to evaluate the efliciency of kinetic data structures when the attribute to be maintained is not canonically defined.

Article Free Access Share on Pipes, cigars, and kreplach: the union of Minkowski sums in three dimensions Authors: Pankaj K. Agarwal Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NCView Profile , Micha Sharir School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 143–153https://doi.org/10.1145/304893.304960Published:13 June 1999Publication History 5citation287DownloadsMetricsTotal Citations5Total Downloads287Last 12 Months8Last 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 SiteeReaderPDF

Let ${\cal F}$ be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the $({\le}k)$-level of the arrangement $\A({\cal F})$ is $O(k^{3+\varepsilon}\psi({n/k}))$ for any $\varepsilon>0$, where $\psi (r)$ is the maximum complexity of the lower envelope of a subset of at most r functions of ${\cal F}$. This bound is nearly optimal in the worst case and implies the existence of shallow cuttings, in the sense of [J. Matousek, Comput. Geom., 2 (1992), pp. 169--186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data structures for several generalized 3-dimensional range-searching problems; (ii) dynamic data structures for planar nearest- and farthest-neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.

International audience

We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.

We show how to preprocess a set S of points in R d into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint x d a 0 + P d 1 i=1 a i x i ; the data structure must report all the points of S that satisfy the constraint. Our goal is to minimize the number of disk blocks required to store the data structure and the number of disk accesses (I/Os) required to answer a query. For d = 2 and d = 3, we present the first near-linear size data structures that can answer linear-constraint queries using an optimal number of I/Os. We also present a linear-size data structures that can answer queries efficiently in the worst case. For the d = 2 case, we also show how to combine these two approaches to obtain tradeoffs between space and query time. Finally, we show that some of our techniques extend to higher dimensions.

We give simple randomized incremental algorithms for computing the Amk-level in an arrangement of n lines in the plane or in an arrangement of n planes in $\Reals^3$. The expected running time of our algorithms is $O(nk+n\alpha(n)\log n)$ for the planarcase and O(nk 2 + n log 3 n) for the three-dimensional case. Both bounds are optimal unless k is very small. The algorithm generalizes to computing the Amk-level in an arrangement of discs or x-monotone Jordan curves in the plane. Our approach can also compute the k-level; this yields a randomized algorithm for computing the order-k Voronoi diagram of n points in the plane in expected time O(k(n-k)log n + n log 3 n).

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized $O(n \log n)$ expected time algorithm for computing $\sqrt{n}$ cells in an arrangement of n lines.

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.

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem.(a) We review sad simplifi some old proofs in new dwguise and give new proofs of the bound O(n~) for the complexity of the k-th level in an arrangement of n lines.(b) We derive an improved version of Lcn%az Lemma in any dimension, and use it to prove a new bound, 0(n2k2/3), on the complexity of the k-th level in an mangement of n planes in lR3, or on the number of k-sets in a set of n points in three dimensions.(c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n312 ), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17'6 ).

We describe the rst known algorithm for efficiently maintaining a Binary Space Partition (BSP) for n continuously moving segments in the plane. Under reasonable assumptions on the motion, we show that the total number of times the BSP changes is O(n²), and that we can update the BSP in O(log n) expected time per change. We also consider the problem of constructing a BSP for n triangles in R³. We present a randomized algorithm that constructs a BSP of expected size O(n²) in O(n² log² n) expected time. We also describe a deterministic algorithm that constructs a BSP of size O((n + k) log n) and height O(log n) in O((n + k) log² n) time, where k is the number of intersection points between the edges of the projections of the triangles onto the xy-plane.

We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R³. We compare known algorithms with our implementation of a recent algorithm of Agarwal et al. [1]. We show via an empirical study that their algorithm constructs BSPs of near-linear size in practice and performs better than

Article Free Access Share on The discrete 2-center problem Authors: Pankaj K. Agarwal Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NCView Profile , Micha Sharir School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile , Emo Welzl Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, Switzerland Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, SwitzerlandView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 147–155https://doi.org/10.1145/262839.262921Published:01 August 1997Publication History 17citation328DownloadsMetricsTotal Citations17Total Downloads328Last 12 Months29Last 6 weeks1 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 SiteeReaderPDF

We present an approximation algorithm that, given the boundary P of a simple, nonconvex polyhedron in R/sup 3/, and two points s and t on P, constructs a path on P between s and t whose length is at most 7(1+/spl epsi/)d/sub P/(s,t), where d/sub P/(s,t) is the length of the shortest path between s and t on P, and /spl epsi/>0 is an arbitrarily small positive constant. The algorithm runs in O(n/sup 5/3/ log/sup 5/3/ n) time, where n is the number of vertices in P. We also present a slightly faster algorithm that runs in O(n/sup 8/5/ log/sup 8/5/ n) time and returns a path whose length is at most 15(1+/spl epsi/)d/sub P/(s,t).

We consider the path-planning problem for a robot pushing an object in an environment containing obstacles. This new variant of the classical robot path-planning problem has several interesting geometric aspects, which we explore. We focus on the setting where the robot makes a point contact with the object which is assumed to be a unit disk, while the obstacles are assumed to be polygonal.

Given a convex polytope P with n faces in ℝ 3 , points ∈ ∂P, and a parameter 0 < ϵ ≤ 1, we present an algorithm that constructs a path on ∂P from s to t whose length is at most (1 + ϵ) d p (s, t) , where d p (s, t) is the length of the shortest path between s and t on ∂P. The algorithm runs in O(n log 1/ϵ + 1/ϵ 3 ) time, and is relatively simple. The running time is O(n + 1/ϵ 3 ) if we only want the approximate shortest path distance and not the path itself. We also present an extension of the algorithm that computes approximate shortest path distances from a given source point on ∂P to all vertices of P .

We introduce the notion of a star unfolding of the surface ${\cal P}$ of a three-dimensional convex polytope with n vertices, and use it to solve several problems related to shortest paths on ${\cal P}$. The first algorithm computes the edge sequences traversed by shortest paths on ${\cal P}$ in time $O(n^6 \beta (n) \log n)$, where $\beta (n)$ is an extremely slowly growing function. A much simpler $O(n^6)$ time algorithm that finds a small superset of all such edge sequences is also sketched. The second algorithm is an $O(n^{8}\log n)$ time procedure for computing the geodesic diameter of ${\cal P}$: the maximum possible separation of two points on ${\cal P}$ with the distance measured along ${\cal P}$. Finally, we describe an algorithm that preprocesses ${\cal P}$ into a data structure that can efficiently answer the queries of the following form: "Given two points, what is the length of the shortest path connecting them?" Given a parameter $1 \le m \le n^2$, it can preprocess ${\cal P}$ in time $O(n^6 m^{1+\delta})$, for any $\delta > 0$, into a data structure of size $O(n^6m^{1+\delta})$, so that a query can be answered in time $O((\sqrt{n}/m^{1/4}) \log n)$. If one query point always lies on an edge of ${\cal P}$, the algorithm can be improved to use $O(n^5 m^{1+\delta})$ preprocessing time and storage and guarantee $O((n/m)^{1/3} \log n)$ query time for any choice of m between 1 and n.

Let ${\cal F}$ be a collection of nd-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of ${\cal F}$ in expected time $O(n^{d+\epsilon})$ for any $\epsilon > 0$. For d = 3, by combining this algorithm with the point-location technique of Preparata and Tamassia, we can compute, in randomized expected time $O(n^{3+\epsilon})$, for any $\epsilon > 0$, a data structure of size $O(n^{3+\epsilon})$ that, for any query point q, can determine in O(log2n) time the function(s) of ${\cal F}$ that attain the lower envelope at q. As a consequence, we obtain improved algorithmic solutions to several problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the "biggest stick" in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in randomized expected time $O(n^{17/11+\epsilon})$, for any $\epsilon > 0$, improving previous solutions that run in time $O(n^{8/5+\epsilon})$. We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require $O(n^{3+\epsilon})$ storage and preprocessing time, for any $\epsilon > 0$, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

The authors consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, nonintersecting, two-dimensional rectangles in R/sup 3/ such that the aspect ratio of each rectangle in S is at most /spl alpha/, for some constant a /spl alpha//spl ges/1. They present an n2/sup O(/spl radic/logn)/-time algorithm to build a binary space partition of size n2/sup O(/spl radic/logn)/ for S. They also show that if m of the n rectangles in S have aspect ratios greater than /spl alpha/, they can contact a BSP of size n/spl radic/m2/sup O(/spl radic/logn)/ for S in n/spl radic/2/sup O(/spl radic/logn)/ time. The constants of proportionality in the big-oh terms are linear in log /spl alpha/. They extend these results to cases in which the input contains non-orthogonal or intersecting objects.

We propose the idea of simplification envelopes for generating a hierarchy of level-of-detail approximations for a given polygonal model.Our approach guarantees that all points of an approximation are within a user-specifiable distance from the original model and that all points of the original model are within a distance from the approximation.Simplification envelopes provide a general framework within which a large collection of existing simplification algorithms can run.We demonstrate this technique in conjunction with two algorithms, one local, the other global.The local algorithm provides a fast method for generating approximations to large input meshes (at least hundreds of thousands of triangles).The global algorithm provides the opportunity to avoid local "minima" and possibly achieve better simplifications as a result.Each approximation attempts to minimize the total number of polygons required to satisfy the above constraint.The key advantages of our approach are: General technique providing guaranteed error bounds for genus-preserving simplification Automation of both the simplification process and the selection of appropriate viewing distances Prevention of self-intersection Preservation of sharp features Allows variation of approximation distance across different portions of a model CR Categories and Subject Descriptors: I.3.

We consider the problem of ray shooting in a three-dimensional scene consisting of m (possibly intersecting) convex polyhedra or polyhedral terrains with a total of n faces, i.e., we want to preprocess them into a data structure, so that the first intersection point of a query ray and the given polyhedra can be determined quickly. We present a technique that requires $O((mn)^{2 + \varepsilon } )$ preprocessing time and storage, and can answer ray-shooting queries in $O(\log ^2 n)$ time. This is a significant improvement over previously known techniques (which require $O(n^{4 + \varepsilon }) $ space and preprocessing) if m is much smaller than n, which is often the case in practice. Next, we present a variant of the technique that requires $O(n^{1 + \varepsilon }) $ space and preprocessing, and answers queries in time $O(m^{{1 / 4}} n^{{1 / 2} + \varepsilon } )$, again a significant improvement over previous techniques when $m \ll n$.

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

Let 3 be a collection of n bivariate algebraic functions of constant maximum degree.We show that the combinatorial complexity of the vertical decomposition of the 0, where @(~) is the maximum complexity of the lower envelope of a subset of at most ~functions of 7.This result implies the existence of shallow cuttings, in the sense of [3, 31], of small size in arrangements of bivariate algebraic functions.We also present numerous applications of these results, including: (i) data structures for several generalized threedimensional range searching problems; (ii) dynamic data structures for planar nearest and farthest neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.

. In this paper we first prove the following combinatorial bound, concerning the complexity of the vertical decomposition of the minimization diagram of trivariate functions: Let F be a collection of n totally or partially defined algebraic trivariate functions of constant maximum degree, with the additional property that, for a given pair of functions f, f # # F , the surface f (x, y, z) = f # (x, y, z) is xy-monotone (actually, we need a somewhat weaker property). We show that the vertical decomposition of the minimization diagram of F consists of O(n 3+# ) cells (each of constant description complexity), for any #>0. In the second part of the paper, we present a general technique that yields faster randomized algorithms for solving a number of geometric optimization problems, including (i) computing the width of a point set in 3-space, (ii) computing the minimum-width annulus enclosing a set of n points in the plane, and (iii) computing the "biggest stick" inside a simpl...

Article Motion planning for a steering-constrained robot through moderate obstacles Share on Authors: Pankaj K. Agarwal Computer Science Department, Duke University, Box 90129, Durham, NC Computer Science Department, Duke University, Box 90129, Durham, NCView Profile , Prabhakar Raghavan IBM T.J. Watson Research Center, Yorktown Heights, NY IBM T.J. Watson Research Center, Yorktown Heights, NYView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, Japan IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, JapanView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 343–352https://doi.org/10.1145/225058.225158Online:29 May 1995Publication History 35citation649DownloadsMetricsTotal Citations35Total Downloads649Last 12 Months11Last 6 weeks1 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

Let K be a set of n non-intersecting objects in 3-space. A depth order of K, if it exists, is a linear order < of the objects in K such that if K, L ϵ K and K lies vertically below L then K < L. We present a new technique for computing depth orders, and apply it to several special classes of objects. Our results include: (i) If K is a set of n triangles whose xy-projections are all ‘fat’, then a depth order for K can be computed in time O(n log5n). (ii) If K is a set of n convex and simply-shaped objects whose xy-projections are all ‘fat’ and their sizes are within a constant ratio from one another, then a depth order for K can be computed in time O(nλs12(n) log4n), where s is the maximum number of intersections between the boundaries of the xy-projections of any pair of objects in K, and λs(n) is the maximum length of (n,s) Davenport-Schinzel sequences.

Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of F in expected time O(nd+ϵ), for any ϵ>0. For d=3, by combining this algorithm with the point location technique of Preparata and Tamassia, we can compute, in randomized expected time O(n3+ϵ) for any ϵ>0, a data structure of size O(n3+ϵ) that, given any query point q, can determine in O(log2n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the biggest stick in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in time O(n17/11+ϵ), for any ϵ>0 improving previous solutions that run in time O(n8/5+ϵ). We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane, and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n3+ϵ) storage and preprocessing time, for any ϵ>0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

We give a simple lazy randomized incremental algorithm to compute ≤k-levels in arrangements of x-monotone Jordan curves in the plane, and in arrangements of planes in three-dimensional space. If each pair of curves intersects in at most s points, the expected running time of the algorithm is O(k2λs(n/k)+min(λs(n)log2n,k2λs(n/k)logn)). For the three-dimensional case the expected running time is O(nk2+min(nlog3n,nk2logn)). The algorithm also works for computing the ≤k-level in a set of discs, with an expected running time of O(nk+min(nlog2n,nklogn)). Furthermore, we give a simple algorithm for computing the order-k Voronoi diagram of a set of n points in the plane that runs in expected time O(k(n−k)logn+nlog3n).

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(nlogn) expected time algorithm for computing √n cells in an arrangement of n lines.

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

Efficient algorithms for the ray shooting problem are presented: Given a collection $\Gamma $ of objects in $\mathbb{R}^d $, build a data structure so that, for a query ray, the first object of $\Gamma $ hit by the ray can be quickly determined. Using the parametric search technique, this problem is reduced to the segment emptiness problem. For various ray shooting problems, space/query-time trade-offs of the following type are achieved: For some integer b and a parameter $m(n \leqslant m \leqslant n^b )$ the queries are answered in time $O(({n / {m^{{1 / b}} }})\log ^{O(1)} n)$, with $O(m^{1 + \varepsilon } )$ space and preprocessing time ($\varepsilon > 0$ is arbitrarily small but fixed constant). $b = \lfloor {{d / 2}} \rfloor $ is obtained for ray shooting in a convex d-polytope defined as an intersection of n half spaces, $b = d$ for an arrangement of n hyperplanes in $\mathbb{R}^d $, and $b = 3$ for an arrangement of n half planes in $\mathbb{R}^3 $. This approach also yields fast procedures for finding the first k objects hit by a query ray, for searching nearest and farthest neighbors, and for the hidden surface removal. All the data structures can be maintained dynamically in amortized time $O({{m^{1 + \varepsilon } } / n})$ per insert/delete operation.

In this paper efficient algorithms for counting intersections in a collection of circles or circular arcs are presented. An algorithm for counting intersections in a collection of n circles is presented whose running time is $O(n^{{3 / {2 + \epsilon }}} )$, for any $\epsilon > 0$ is presented. Using this algorithm as a subroutine, it is shown that the intersections in a set of n circular arcs can also be counted in time $O(n^{{3 / {2 + \epsilon }}} )$. If all arcs have the same radius, the running time can be improved to $O(n^{{4 / {3 + \epsilon }}} )$, for any $\epsilon > 0$.

The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree.>

Efficient algorithms for the ray shooting problem are presented: Given a collection F of objects in d, build a data structure so that, for a query ray, the first object of F hit by the ray can be quickly determined. Using the parametric search technique, this problem is reduced to the segment emptiness problem. For various ray shooting problems, space/query-time trade-offs of the following type are achieved: For some integer b and a parameter m (n _< m < n b) the queries are answered in time O((n/m /b) log <) n), with O(m!+) space and preprocessing time (t> 0 is arbitrarily small but fixed constant), b Ld/2J is obtained for ray shooting in a convex d-polytope defined as an intersection of n half spaces, b d for an arrangement of n hyperplanes in d, and b 3 for an arrangement of n half planes in 3. This approach also yields fast procedures for finding the first k objects hit by a query ray, for searching nearest and farthest neighbors, and for the hidden surface removal. All the data structures can be maintained dynamically in amortized time O (m + / n) per insert/delete operation.

This paper considers the following problem: Given a set $\mathcal{G}$ of n (possibly intersecting) line segments in the plane, preprocess it so that, given a query ray $\rho $ emanating from a point p, one can quickly compute the intersection point $\Phi (\mathcal{G},\rho )$ of $\rho $ with a segment of $\mathcal{G}$ that lies nearest to p. The paper presents an algorithm that preprocesses $\mathcal{G}$, in time $O(n^{3/ 2} \log^\omega n)$, into a data structure of size $O(n\alpha (n)\log ^4 n)$, so that for a query ray $\rho $, $\Phi (\mathcal{G},\rho )$ can be computed in time $O(\sqrt {n\alpha (n)} \log ^2 n)$, where $\omega $ is a constant $ < 4.33$ and $\alpha (n)$ is a functional inverse of Ackermann’s function. If the given segments are nonintersecting, the storage goes down to $O(n\log ^3 n)$ and the query time becomes $O(\sqrt n \log ^2 n)$. The main tool used is spanning trees (on the set of segment endpoints) with low stabbing number, i.e., with the property that no line intersects more than $O(\sqrt n )$ edges of the tree. Such trees make it possible to obtain faster algorithms for several other problems, including implicit point location, polygon containment, and implicit hidden surface removal.

The following class of query problems is studied: Given a set of n arcs (disks, circles, circular arcs, Jordan arcs) in the plane, preprocess it into a data structure, such that for a query line (or segment) 1, one can quickly (i) report all arcs intersecting /?, or (ii) count the number of arcs intersecting L We also stud y the ray shooting problem for disjoint Jordan arcs and for circular arcs.Most of the data structures presented here use linear or near to linear space and have query time near to 0(/E+K) or 0(n2/3+K), where K is the size of the output.The query time of some of our algorithms can be improved by allowing more space.

In this paper we present efficient algorithms for counting intersections in a collection of circles or circular arcs.YVe present a randomized algorithm to count intersections in a collection of n circles whose expected running time is 0(n3i2+C), for any c > 0. We also develop another randomized algorithm to count intersections in a set of n circular arcs whose expected running time is O(n513+C), for any ~> 0. If all arcs have the same radius, the (expected) running time can he improved to 0(n312+C), for any c > 0.

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.

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.

We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in @@@@d in time 𝒪(Τd(N, N) logd N), where Τd(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in @@@@d. If Τd(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to 𝒪(Τd(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time 𝒪((nm log n log m)2/3 + m log2 n + n log2 m) in @@@@3, which yields an 𝒪(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in @@@@3.

Abstract The general rectilinear Steiner tree problem has been proved to be NP‐complete. In this paper, we consider a special case in which the points lie on the boundary of a rectilinear rectangle and give anO(n)algorithm to construct a minimum rectilinear Steiner tree for such points.

Let ${\bf \Gamma }$ be a collection of n (possibly intersecting) “red” Jordan arcs of some simple shape in the plane and let ${\bf \Gamma }^{\prime}$ be a similar collection of m “blue” arcs. Several efficient algorithms are presented for detecting an intersection between an arc of ${\bf \Gamma }$ and an arc of ${\bf \Gamma }^{\prime}$. (i) If the arcs of ${\bf \Gamma }^{\prime}$ form the boundary of a simply connected region, then the following can be detected: a “red-blue” intersection in time $O(\lambda _s (m) \log ^2 m+(\lambda _s (m)+n) \log (n+m))$ where $\lambda _s (m)$ is the (almost-linear) maximum length of $(m, s)$ Davenport–Schinzel sequences, and where s is a fixed parameter, depending on the shape of the given arcs. Another case where an intersection in close to linear time can be detected is when the union of the arcs of ${\bf \Gamma }$ and the union of the arcs of ${\bf \Gamma }^{\prime}$ are both connected. (ii) In the most general case, an intersection in time $O((m\sqrt {\lambda _s (n)} + n\sqrt {\lambda _s (m)} )\log ^{1.5} (m + n))$ can be detected. For several special but useful cases, in which many faces in the arrangements of ${\bf \Gamma }$ and ${\bf \Gamma }^{\prime}$ can be computed efficiently, randomized algorithms that are better than the general algorithm are obtained. In particular when all arcs in ${\bf \Gamma }$ and ${\bf \Gamma }^{\prime}$ are line segments, a randomized $O((m + n)^{{4 / 3}+\varepsilon})$ intersection detection algorithm, for any $\varepsilon > 0$, is obtained. The algorithm in (i) is applied to obtain an $O(\lambda _s (n) \log ^2 n)$ algorithm (for some small $s > 0$) for planning the motion of an n-sided simple polygon around a right-angle corner in a corridor, improving a previous $O(n^{2})$ algorithm of [Proc. 4th Annual Symposium on Computational Geometry, Association for Computing Machinery, New York, 1988, pp. 187–192], and to derive an efficient technique for fast collision detection for a simple polygon moving (translating and rotating) in the plane along a prescribed path.

In this paper we consider the following problem: Given a set ℒ of n lines in the plane, partition the plane into Ο(r2) triangles so that no triangle intersects more than Ο(n/r) lines of ℒ. We present a deterministic algorithm for this problem with Ο(nr log n logω r) running time, where ω is a constant < 3.3. Our algorithm is faster than Matousk's recent algorithm [Ma] for large values of r. In the second part of the paper, we apply this algorithm to several problems involving lines or segments in the plane, and obtain deterministic algorithms which are faster than any previously known algorithms. For example we give an Ο(n2/3m2/3 log n logω/3 m/√n + (m + n) log n) algorithm to compute all incidences between m points and n lines. Other problems include computing many faces in an arrangement of lines or segments, counting segment intersections, red-blue intersection detection, simplex range queries and computing stabbing trees with low stabbing number.

@ of n (possibly intersecting) line segments in the plane, preprocess them so that, given a query ray r emanating from a point p, we can quickly compute the intersection point P(

Let Γ be a collection of n (possibly intersecting) “red” Jordan arcs of some simple shape in the plane and let Γ' be a similar collection of m “blue” arcs. We present several efficient algorithms for detecting an intersection between an arc of Γ and an arc of Γ'. (i) If the arcs of Γ' form the boundary of a simply connected region, then we can detect a “red-blue” intersection in time Ο (λs(m)log2 m + (λa(m) + n)log(n + m)) where λs(m) is the (almost-linear) maximum length of (m, s) Davenport-Schinzel sequences, and where s is a fixed parameter, depending on the shape of the given arcs. Another case where we can detect an intersection in close to linear time is when the union of the arcs of Γ and the union of the arcs of Γ' are both connected. (ii) In the most general case, we can detect an intersection in time Ο ((m√λs(n) + n√λs(m))log1.5(m+n)). For several special but useful cases, in which many faces in the arrangements of Γ and Γ' can be computed efficiently, we obtain randomized algorithms which are better than the general algorithm. In particular when all arcs in Γ and Γ' are line segments, we obtain a randomized Ο((m+n)4/3+c) intersection detection algorithm.