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.

Let P be a set of n points in ℝ^d, d ≥ 2, and let t ≥ 2 be an integer. Let H_t(P) denote the t-uniform hypergraph on P, whose hyperedges consist of all t-tuples T ⊂ P for which ‖p-q‖ ≤ 1, for any two points p,q ∈ T. A matching in H_t(P) is a collection of vertex-disjoint hyperedges. We present a PTAS for finding a maximum matching in H_t(P). In particular, we present the first PTAS for the well-studied problem known as maximum (vertex-disjoint) triangle packing in unit disk graphs. Our approach consists of a sparsification stage, which replaces P by a subset Q with favorable properties, followed by an implementation of a PTAS for a maximum matching in H_t(Q). The two stages follow the high-level machinery in [Édouard Bonnet et al., 2023] and [Rom Aschner et al., 2013], respectively, but are considerably more involved.

We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna angles bounded from below by a constant, and visibility graphs whose vertices lie on or above a 1.5-dimensional terrain, both with Euclidean distances as edge weights. We provide near-linear algorithms for the corresponding decision problems, namely, determining whether the subgraph obtained by retaining all edges with weight at most some threshold bn contains a path from s to t. We then use the decision procedures to obtain algorithms for the bottleneck path problem that run in O^*(n^{8/7}) randomized expected time, where n is the input size and the O^*(⋅) notation hides subpolynomial factors. Within the same performance bounds, we can also solve the bounded-hop version, in which we only consider s-t paths with at most k edges, for a given integer k < n.

Let $P$ be a polygonal curve with $n$ vertices in the plane. We construct a data structure of size $O(n \log n)$ suited for simplification queries of the following kind. Given a query line $\ell$ and an integer $k\ge1$, find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to $P$, among all such curves. Using our data structure, a query can be handled in $O(k^2 \log^3 n + k\log^4 n)$ time. More generally, a geometric tree $T$ on $n$ vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair $u$, $v$ of its vertices, a line $\ell$, and an integer $k\ge1$, one can find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to the path from $u$ to $v$ in $T$, in time $O(k^2 \mathop{polylog} n)$. For the general dimension-reduction problem, where $P$ is a curve in $\mathbb{R}^d$ ($d \ge 3$), $0 < \varepsilon_0 < 1$ is a real parameter, and a query specifies a $g$-flat $h$ ($1 \le g \le d-1$) and an integer $k \ge 1$, we construct a data structure of size $O(n\log n + f(\varepsilon_0) n)$, where $f(\varepsilon_0)=(1+1/\varepsilon_0)^{(d-1)/2}$, that allows us to find a curve $Q$ on $h$ with at most $k$ vertices, whose discrete Fréchet distance to $P$ is at most $1+\varepsilon_0$ times the distance of $Q^*$ to $P$, where $Q^*$ is such a curve that minimizes the distance to $P$. The query handling time is $O(f(\varepsilon_0) k^2 \log^2 n)$.

Let ℬ be a collection of n arbitrary balls in ℝ³, and let G₀(ℬ) be their intersection graph. We provide an algorithm for performing BFS on G₀(ℬ), which runs in O^*(n^{4/3}) time, where the O^*(⋅) notation hides subpolynomial factors. For r ≥ 0, let G_r(ℬ) be the intersection graph of the set ℬ_r = {B+r ∣ B ∈ ℬ}, where B+r is the ball concentric with B whose radius is larger by r than the radius of B. We provide an efficient algorithm for the reverse shortest path (RSP) problem, where we are given two designated balls B_s, B_t of ℬ and a parameter 0 < λ < n, and seek the smallest value r^* for which G_{r^*}(ℬ) contains a path from B_s to B_t of at most λ edges. For the special case of congruent balls (equivalently, for points in ℝ³), the algorithm runs in O^*(n^{29/21}) ≈ O^*(n^{1.381}) time. For the general case, the algorithm runs in O^*(n^{56/39}) ≈ O^*(n^{1.436}) time. We also extend the technique to handle other measures of expansion and higher dimensions.

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.

It is unlikely that the discrete Fréchet distance between two curves of length $n$ can be computed in strictly subquadratic time. We thus consider the setting where one of the curves, $P$, is known in advance. In particular, we wish to construct data structures (distance oracles) of near-linear size that support efficient distance queries with respect to $P$ in sublinear time. Since there is evidence that this is impossible for query curves of length $Θ(n^α)$, for any $α> 0$, we focus on query curves of (small) constant length, for which we are able to devise distance oracles with the desired bounds. We extend our tools to handle subcurves of the given curve, and even arbitrary vertex-to-vertex subcurves of a given geometric tree. That is, we construct an oracle that can quickly compute the distance between a short polygonal path (the query) and a path in the preprocessed tree between two query-specified vertices. Moreover, we define a new family of geometric graphs, $t$-local graphs (which strictly contains the family of geometric spanners with constant stretch), for which a similar oracle exists: we can preprocess a graph $G$ in the family, so that, given a query segment and a pair $u,v$ of vertices in $G$, one can quickly compute the smallest discrete Fréchet distance between the segment and any $(u,v)$-path in $G$. The answer is exact, if $t=1$, and approximate if $t>1$.

We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor 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.

We present a general technique, based on parametric search with some twist, for solving a variety of optimization problems on a set of semi-algebraic geometric objects of constant complexity. The common feature of these problems is that they involve a `growth parameter' $r$ and a semi-algebraic predicate $Π(o,o';r)$ of constant complexity on pairs of input objects, which depends on $r$ and is monotone in $r$. One then defines a graph $G(r)$ whose edges are all the pairs $(o,o')$ for which $Π(o,o';r)$ is true, and seeks the smallest value of $r$ for which some monotone property holds for $G(r)$. Problems that fit into this context include (i) the reverse shortest path problem in unit-disk graphs, recently studied by Wang and Zhao, (ii) the same problem for weighted unit-disk graphs, with a decision procedure recently provided by Wang and Xue, (iii) extensions of these problems to three and higher dimensions, (iv) the discrete Fréchet distance with one-sided shortcuts in higher dimensions, extending the study by Ben Avraham et al., (v) perfect matchings in intersection graphs: given, e.g., a set of fat ellipses of roughly the same size, find the smallest value $r$ such that if we expand each of the ellipses by $r$, the resulting intersection graph contains a perfect matching, (vi) generalized distance selection problems: given, e.g., a set of disjoint segments, find the $k$'th smallest distance among the pairwise distances determined by the segments, for a given (sufficiently small but superlinear) parameter $k$, and (vii) the maximum-height independent towers problem, in which we want to erect vertical towers of maximum height over a 1.5-dimensional terrain so that no pair of tower tips are mutually visible. We obtain significantly improved solutions for problems (i), (ii) and (vi), and new efficient solutions to the other problems.

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

In the (1+ε,r)-approximate near-neighbor problem for curves (ANNC) under some similarity measure δ, the goal is to construct a data structure for a given set 𝒞 of curves that supports approximate near-neighbor queries: Given a query curve Q, if there exists a curve C ∈ 𝒞 such that δ(Q,C)≤ r, then return a curve C' ∈ 𝒞 with δ(Q,C') ≤ (1+ε)r. There exists an efficient reduction from the (1+ε)-approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve C ∈ 𝒞 with δ(Q,C) ≤ (1+ε)⋅δ(Q,C^*), where C^* is the curve of 𝒞 most similar to Q. Given a set 𝒞 of n curves, each consisting of m points in d dimensions, we construct a data structure for ANNC that uses n⋅ O(1/ε)^{md} storage space and has O(md) query time (for a query curve of length m), where the similarity measure between two curves is their discrete Fréchet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared to all previous bounds. Further, we also consider the asymmetric version of ANNC, where the length of the query curves is k ≪ m, and obtain essentially the same storage and query bounds as above, except that m is replaced by k. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds.

Dynamic Time Warping (DTW) is a well-known similarity measure for curves, i.e., sequences of points, and especially for time series. We study several proximity problems for curves, where dynamic time warping is the underlying similarity measure. More precisely, we focus on the variants of these problems, in which, whenever we refer to the dynamic time warping distance between two curves, one of them is a line segment (i.e., a sequence of length two). These variants already reveal some of the difficulties that occur when dealing with the more general ones. Specifically, we study the following three problems: (i) distance oracle: given a curve C in ℝ^d, preprocess it to accommodate distance computations between query segments and C, (ii) segment center: given a set 𝒞 of curves in ℝ^d, find a segment s that minimizes the maximum distance between s and a curve in 𝒞, and (iii) segment nearest neighbor: given 𝒞, construct a data structure for segment nearest neighbor queries, i.e., return the curve in 𝒞 which is closest to a query segment s. We present solutions to these problems in any constant dimension d ≥ 1, using L_∞ for inter-point distances. We also consider the approximation version of the first problem, using L₁ for inter-point distances. That is, given a length-m curve C in ℝ^d, we construct a data structure of size O(m log m) that allows one to compute a 2-approximation of the distance between a query segment s and C in O(log³ m) time. Finally, we describe an interesting experimental study that we performed, which is related to the first problem above.

We consider a set of transmitters broadcasting simultaneously on the same frequency under the signal to interference plus noise ratio (SINR) model. Transmission power may vary from one transmitter to another, and a transmitter's signal strength at a given point is modeled by the transmitter's power divided by some constant power $\alpha$ of the distance it traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger by a specified ratio than the signals of all other transmitters combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite yes or definite no, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either yes or no. We describe compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where transmitters may be inserted and deleted over time. We distinguish between two main variants---uniform power and nonuniform power. In both variants the preprocessing time is $O(n\,{polylog} n)$ and the amortized update time is $O({\rm polylog} n)$, while the query time is $O({polylog} n)$ for uniform power, and randomized time $O(\sqrt{n}\,{polylog} n)$ with high probability for nonuniform power. Finally, we observe that in the static context the latter data structure can be implemented differently, so that the query time is also $O({polylog} n)$, thus significantly improving all previous results for this problem.

Let A and B be two sets of points in R^d, where |A|=|B|=n and the distance between them is defined by some bipartite measure dist(A, B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are (i) the diameter in two and three dimensions, that is diam(A,B) = max {d(a,b) | a in A, b in B}, where d(a,b) is the Euclidean distance between a and b, (ii) the uniformity in the plane, that is uni(A,B) = diam(A,B) - d(A,B), where d(A,B)=min{d(a,b) | a in A, b in B}, and (iii) the union width in two and three dimensions, that is union_width(A,B) = width(A cup B). For each of these measures we present efficient algorithms for finding a translation of B that minimizes the distance: For diameter we present near-linear-time algorithms in R^2 and R^3, for uniformity we describe a roughly O(n^{9/4})-time algorithm, and for union width we offer a near-linear-time algorithm in R^2 and a quadratic-time one in R^3.

Given $n$ pairs of points, $\mathcal{S} = \{\{p_1, q_1\}, \{p_2, q_2\}, \dots, \{p_n, q_n\}\}$, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.

In this paper, we study the problem of data gathering in ad-hoc sensor networks using a mobile entity called mule. The mule traverses the children of failed sensors, to prevent loss of data. Our objective is to define the optimal communication tree and the mule's placement such that the mule's overall traveling distance is minimized. We explore this problem in several network topologies including: unit disc graph on a line (UDL), general unit disc graph (UDG), and a complete graph with failing probabilities on the nodes (CGFP). We provide an optimal solution for the UDL problem and two approximation algorithms for the UDG problem. For the CGFP problem we outline the two possible structures of an optimal solution and provide near optimal approximation algorithms.

We show that for any set of n moving points in R^d and any parameter 2<=k

The Chain Pair Simplification problem (CPS) was posed by Bereg et al. who were motivated by the problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones. In this problem, given two polygonal chains of lengths n and m, the goal is to simplify both of them simultaneously, so that the lengths of the resulting simplifications as well as the discrete Frechet distance between them are bounded. When the vertices of the simplifications are arbitrary (i.e., not necessarily from the original chains), the problem is called General CPS (GCPS). In this paper we consider for the first time the complexity of GCPS under both the discrete Frechet distance (GCPS-3F) and the Hausdorff distance (GCPS-2H). (In the former version, the quality of the two simplifications is measured by the discrete Fr'echet distance, and in the latter version it is measured by the Hausdorff distance.) We prove that GCPS-3F is polynomially solvable, by presenting an widetilde-O((n+m)^6 min{n,m}) time algorithm for the corresponding minimization problem. We also present an O((n+m)^4) 2-approximation algorithm for the problem. On the other hand, we show that GCPS-2H is NP-complete, and present an approximation algorithm for the problem.

The SINR model for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the SINR diagram, which partitions the space into n regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard. Efficient point location in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several papers. These planar data structures are constructed in time at least quadratic in n and support logarithmic-time approximate queries. Moreover, the performance of some of the proposed structures depends strongly not only on the number n of transmitters and on the approximation parameter $$\varepsilon $$ , but also on some geometric parameters that cannot be bounded a priori as a function of n or $$\varepsilon $$ . In this paper, we address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer n queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. All these results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on n and $$\varepsilon $$ . Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields.

The Fréchet distance is a well-studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fréchet distance with shortcuts , which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in O (( m + n ) 6/5 + ε ) expected time, for any ε > 0. When shortcuts are allowed in both curves, we give an O (( m 2/3 n 2/3 + m + n )log 3 ( m + n ))-time deterministic algorithm. We also consider the semicontinuous Fréchet distance with one-sided shortcuts, where we have a sequence of m points and a polygonal curve of n edges, and shortcuts are allowed only in the sequence. We show that this problem can be solved in randomized expected time O (( m + n ) 2/3 m 2/3 n 1/3 log ( m + n )). Our techniques are novel and may find further applications. One of the main new technical results is: Given two sets of points A and B in the plane and an interval I , we develop an algorithm that decides whether the number of pairs ( x , y ) ∈ A × B whose distance dist( x , y ) is in I is less than some given threshold L . The running time of this algorithm decreases as L increases. In case there are more than L pairs of points whose distance is in I , we can get a small sample of pairs that contain a pair at approximate median distance (i.e., we can approximately “bisect” I ). We combine this procedure with additional ideas to search, with a small overhead, for the optimal one-sided Fréchet distance with shortcuts, using a very fast decision procedure. We also show how to apply this technique for approximating distance selection (with respect to rank), and a somewhat more involved variant of this technique is used in the solution of the semicontinuous Fréchet distance with one-sided shortcuts. In general, the new technique can be applied to optimization problems for which the decision procedure is very fast but standard techniques like parametric search makes the optimization algorithm substantially slower.

We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using "t-spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t-spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.

The Fréchet distance is a well studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fréchet distance with shortcuts, which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in O((m+n)6/5+ϵ) expected time, for any ϵ > 0. When shortcuts are allowed in both curves, we give an O((m2/3n2/3 + m + n) log3(m + n))-time deterministic algorithm.

We consider a geometric optimization problem that arises in network design. Given a set P of n points in the plane, source and destination points s,t ∈ P, and an integer k > 0, one has to locate k Steiner points, such that the length of the longest edge of a bottleneck path between s and t is minimized. In this paper, we present an O(n log2 n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. [Hou10], who gave an O(n2log n)-time algorithm. We also study the dual version of the problem, where a value λ > 0 is given (instead of k), and the goal is to locate as few Steiner points as possible, so that the length of the longest edge of a bottleneck path between s and t is at most λ.

Let P be a simple polygon, and let Q be a set of points in P. We present an almost-linear time algorithm for computing a minimum cover of Q by disks that are contained in P. We then generalize the algorithm so that it can compute a minimum cover of Q by homothets of any fixed compact convex set ${\cal O}$ of constant description complexity that are contained in P. This improves previous results of Katz and Morgenstern [Lecture Notes in Comput. Sci. 5664, 2009, pp. 447–458]. We also consider the minimum disk-cover problem when Q is contained in a (sufficiently narrow) annulus and present a nearly linear algorithm for this case, too.

A power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. The cost of a power assignment is the sum of the powers. The energy of a transmission path from node u to node v is the sum of the squares of the distances between adjacent nodes along the path. For a constant t > 1, an energy t-spanner is a graph G', such that for any two nodes u and v, there exists a path from u to v in G', whose energy is at most t times the energy of a minimum-energy path from a ton in the complete Euclidean graph. In this paper, we study the problem of finding a power assignment, such that (i) its induced communication graph is a 'good' energy spanner, and (ii) its cost is 'low'. We show that for any constant t > 1, one can find a power assignment, such that its induced communication graph is an energy t-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph). This is a very significant improvement over the best current result due to Shpungin and Segal, presented in last year's conference.

We present the first constant‐factor approximation algorithm for a nontrivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an $O(1)$‐approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic‐factor approximations follow from set cover results, our new results exploit the geometric structure of terrains to obtain a substantially improved approximation algorithm.

We consider the problem of balancing the load among several service-providing facilities, while keeping the total cost low. Let D be the underlying demand region, and let p1, …, pm be m points representing m facilities. We consider the following problem: Subdivide D into m equal-area regions R1, …, Rm, so that region Ri is served by facility pi, and the average distance between a point q in D and the facility that serves q is minimal.We present constant-factor approximation algorithms for this problem, with the additional requirement that the resulting regions must be convex. As an intermediate result we show how to partition a convex polygon into m=2k equal-area convex subregions so that the fatness of the resulting regions is within a constant factor of the fatness of the original polygon. We also prove that our partition is, up to a constant factor, the best one can get if one's goal is to maximize the fatness of the least fat subregion.We also discuss the structure of the optimal partition for the aforementioned load balancing problem: indeed, we argue that it is always induced by an additive-weighted Voronoi diagram for an appropriate choice of weights.

We study the problem of computing the visibility graph defined by a set P of n points inside a polygon Q: two points p,q ε P are joined by an edge if the segment ‾pq ⊂ Q. Efficient output-sensitive algorithms are known for the case in which P is the set of all vertices of Q. We examine the general case in which P is an arbitrary set of points, interior or on the boundary of Q and study a variety of algorithmic questions. We give an output-sensitive algorithm, which is nearly optimal, when Q is a simple polygon. We introduce a notion of "fat" or "robust" visibility, and give a nearly optimal algorithm for computing visibility graphs according to it, in polygons Q that may have holes. Other results include an algorithm to detect if there are any visible pairs among P, and algorithms for output-sensitive computation of visibility graphs with distance restrictions, invisibility graphs, and rectangle visibility graphs.

The terrain surface simplification problem has been studied extensively, as it has important applications in geographic information systems and computer graphics. The goal is to obtain a new surface that is combinatorially as simple as possible, while maintaining a prescribed degree of similarity with the original input surface. Generally, the approximation error is measured with respect to distance (e.g., Hausdorff) from the original or with respect to visual similarity. In this paper, we propose a new method of simplifying terrain surfaces, designed specifically to maximize a new measure of quality based on preserving inter-point visibility relationships. Our work is motivated by various problems of terrain analysis that rely on inter-point visibility relationships, such as optimal antenna placement.We have implemented our new method and give experimental evidence of its effectiveness in simplifying terrains according to our quality measure. We experimentally compare its performance with that of other leading simplification methods.

We study several natural proximity and facility location problems that arise for a set ${\cal P}$ of $n$ points and a set $\R$ of $m$ disjoint rectangular obstacles in the plane, where distances are measured according to the $L_1$ shortest path (geodesic) metric. In particular, we compute, in time $O(mn\log(m+n))$, a data structure of size $O(mn)$ that supports $O(\log(m+n))$-time farthest point queries; we avoid computing the more complicated farthest neighbor Voronoi diagram, whose combinatorial complexity we show to be $\Theta(mn)$. We study the center point problem, finding in $O(mn\log(m+n))$ time a center point (and the set of center points) that minimize the maximum distance to sites of ${\cal P}$; this result improves the best previous bound by a factor of roughly $m$. In addition, we give algorithms for approximating the diameter, $D$, and radius, $r$, of ${\cal P}$, including methods to (i) compute a pair of points $a,b \in {\cal P}$, such that $d(a,b) \ge (1-\eps)D$, in $O(n\log n + \frac{1}{\eps}(n+m) \log m)$ time; and (ii) compute a point $c'$, such that $\max \{d(p, c') \ | \ p \in {\cal P}\} \le (1+\eps)r$, in $O(n\log(m+n) + (m/\eps)\log(m+1/\eps))$ time. Finally, we show that for all the problems above it is enough to consider only a subset of ${\cal P}$. This subset is likely to be much smaller than ${\cal P}$, it is computable in $O(n \log n)$ time, and using it results in significantly decreased runtime in practice.

We show that the maximum number of geometric permutations of a set of $n$ pairwise-disjoint convex and fat objects in $\reals^d$ is $O(n^{d-1})$. This generalizes the bound of $\Theta (n^{d-1})$ obtained by Smorodinsky et al. \cite{ssm98} on the number of geometric permutations of $n$ pairwise-disjoint balls.

Article On the union of κ-curved objects Share on Authors: Alon Efrat Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel Department of Computer Science, Tel-Aviv University, Tel-Aviv 69978, IsraelView Profile , Matthew J. Katz Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva S4105, Israel Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva S4105, IsraelView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 206–213https://doi.org/10.1145/276884.276908Online:07 June 1998Publication History 9citation161DownloadsMetricsTotal Citations9Total Downloads161Last 12 Months1Last 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

Many algorithms developed in computationid geometry are needlessly complicated and slow because they have to be prepared for very complicated, hypathetical inputs.To avoid this, realistic models are needed that describe the properties that realistic inputs have, so that algorithms can de designed that take advantage of these properties.This can lead to algorithms that are provably efficient in realktic situations.We obtain some fundamental results in this research direction.In particular, we have the following results.. We show the relations between various models that have been proposed in the literature.q For several of these models, we give algorithms to compute the model parameter(s) for a given scene; these algorithms can be used to verify whether a model is appropriate for typical scenesin some application area.q As a case study, we give some experimental results on the appropriateness of some of the models for one particular type of scenes often encountered in GIS, namely certain triangulated irregular networks.

We present a new approach to problems in geometric optimization that are traditionally solved using the parametric-searching technique of Megiddo [J. ACM, 30 (1983), pp. 852--865]. Our new approach is based on expander graphs and range-searching techniques. It is conceptually simpler, has more explicit geometric flavor, and does not require parallelization or randomization. In certain cases, our approach yields algorithms that are asymptotically faster than those currently known (e.g., the second and third problems below) by incorporating into our (basic) technique a subtechnique that is equivalent to (though much more flexible than) Cole's technique for speeding up parametric searching [J. ACM, 34 (1987), pp. 200--208]. We exemplify the technique on three main problems---the slope selection problem, the planar distance selection problem, and the planar {\em two-line center} problem. For the first problem we develop an $O(n\log^3 n)$ solution, which, although suboptimal, is very simple. The other two problems are more typical examples of our approach. Our solutions have running time $O(n^{4/3}\log^2n)$ and $O(n^2 \log^4 n)$, respectively, slightly better than the previous respective solutions of [Agarwal et al., Algorithmica, 9 (1993), pp. 495--514], [Agarwal and Sharir, Algorithmica, 11 (1994), pp. 185--195]. We also briefly mention two other problems that can be solved efficiently by our technique. In solving these problems, we also obtain some auxiliary results concerning batched range searching, where the ranges are congruent discs or annuli. For example, we show that it is possible to compute deterministically a compact representation of the set of all point-disc incidences among a set of n congruent discs and a set of m points in the plane in time $O((m^{2/3} n^{2/3}+m+n)\log n)$, again slightly better than what was previously known.

A set of objects is k-pierceable if there exists a set of k points such that each object is pierced by (contains) at least one of these points.Finding the smallest integer k such that a set is k-pierceable is NP-complete.In this paper, we present efficient algorithms for findinga piercing set (i.e., a set ofkpoints asabove) for several classes of convex objects and small values of k.In some of the cases, our algorithms imply known as well as new Helly-type theorems, thus adding to previous results of Danzer and Griinbaum who studied the case of axisparallel boxes.The problems studied here are related to the collection of optimization problems in which one seeks the smallest scaling factor of a centrally symmetric convex object K, so that a set of points can be covered by k congruent homothets of K. h = h(C, P)associated with a class of objects C and a property P is

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.

We present a new approach to problems in geometric optimization that are traditionally solved using the parametric searching technique of Megiddo. Our new approach is based on expander graphs and is conceptually much simpler and has more explicit geometric flavor. It does not require parallelization or randomization, and it exploits recent range-searching techniques of Matousˇek and others. We exemplify the technique on three problems, the slope selection problem, the planar distance selection problem, and the planar two-center problem. For the first problem we develop an O(n log3n)) solution, which, although suboptimal, is very simple. The second and third problems are more typical examples of our approach. Our solutions have, respectively, running time O(n4/3 log3+δ n), for any δ > 0, and O(n2 log3 n), comparable with the respective solutions of [2, 5].

Given n points in the plane and an integer k, the slope selection problem is to find the pair of points whose connecting line has the kth smallest slope. (In dual setting, given n lines in the plane, we want to find the vertex of their arrangement with the kth smallest x-coordinate.) Cole et al. have given an O(n log n) solution (which is optimal), using the parametric searching technique of Megiddo. We obtain another optimal (deterministic) solution that does not depend on parametric searching and uses expander graphs instead. Our solution is somewhat simpler than that of [6] and has a more explicit geometric interpretation.

Research in distributed artificial intelligence planning has historically focused on two distinct classes of problems. One paradigm has been that of 'planning for multiple agents', which considers issues inherent in centrally directed multi-agent execution. The second paradigm has been 'distributed planning', where multiple agents more autonomously participate in coordinating and deciding upon their own actions. The work described in this paper is in the first category, planning for multiple agents. Taking the STRIPS representation of actions, and directed acrylic graphs (DAGs) as plan representations particularly well suited to parallel execution, it formally analyses the following question: how can a DAG plan be verified (i.e. how can we be sure such a plan will be correct, given our uncertainty about exactly when unconstrained parallel actions will be performed)? A method is presented for verifying the correctness of plans for multiple agents, represented as DAGs. The technique allows for the efficient analysis of a plan, despite its many potential execution histories.

methods also apply to computing the vi;lbility map for a polyhedral terrain viewed from a fixed point, and yield O((rm(n) + k) log n) algorithms.