Given the compressed sensing measurements of an unknown vector $z \in \mathbb{R}^n$ using random matrices, we present a simple method to determine $z$ without solving any optimization problem or linear system. Our method uses $Θ(\log n)$ random sensing matrices in $\mathbb{R}^{k \times n}$ and runs in $O(kn\log n)$ time, where $k = Θ(s\log n)$ and $s$ is the number of nonzero coordinates in $z$. We adapt our method to determine the support set of $z$ and experimentally compare with some optimization-based methods on binary signals.

While there are software systems that simplify trajectory streams on the fly, few curve simplification algorithms with quality guarantees fit the streaming requirements. We present streaming algorithms for two such problems under the Fréchet distance d_F in ℝ^d for some constant d ≥ 2. Consider a polygonal curve τ in ℝ^d in a stream. We present a streaming algorithm that, for any ε ∈ (0,1) and δ > 0, produces a curve σ such that d_F(σ,τ[v₁,v_i]) ≤ (1+ε)δ and |σ| ≤ 2 opt-2, where τ[v₁,v_i] is the prefix in the stream so far, and opt = min{|σ'|: d_F(σ',τ[v₁,v_i]) ≤ δ}. Let α = 2(d-1)⌊d/2⌋² + d. The working storage is O(ε^{-α}). Each vertex is processed in O(ε^{-α} log 1/ε) time for d ∈ {2,3} and O(ε^{-α}) time for d ≥ 4 . Thus, the whole τ can be simplified in O(ε^{-α}|τ| log 1/ε) time. Ignoring polynomial factors in 1/ε, this running time is a factor |τ| faster than the best static algorithm that offers the same guarantees. We present another streaming algorithm that, for any integer k ≥ 2 and any ε ∈ (0,1/17), maintains a curve σ such that |σ| ≤ 2k-2 and d_F(σ,τ[v₁,v_i]) ≤ (1+ε) ⋅ min{d_F(σ',τ[v₁,v_i]): |σ'| ≤ k}, where τ[v₁,v_i] is the prefix in the stream so far. The working storage is O((kε^{-1}+ε^{-(α+1)})log 1/(ε)). Each vertex is processed in O(kε^{-(α+1)}log²1/(ε)) time for d ∈ {2,3} and O(kε^{-(α+1)} log 1/ε) time for d ≥ 4.

Let m and n be the numbers of vertices of two polygonal curves in ℝd for any fixed d such that m ≤ n. Since it was known in 1995 how to compute the Fréchet distance of these two curves in O (mn log(mn )) time, it has been an open problem whether the running time can be reduced to o (n2) when m = Ω(n ). In the mean time, several well-known quadratic time barriers in computational geometry have been overcome: 3SUM, some 3SUM-hard problems, and the computation of some distances between two polygonal curves, including discrete Fréchet distance, dynamic time warping, and geometric edit distance. It is curious that the quadratic time barrier for Fréchet distance still stands. We present an algorithm to compute the Fréchet distance in O (mn (log log n )2+μ log n/ log1+μ m ) expected time for some constant μ ∈ (0,1). It is the first algorithm that returns the Fréchet distance in o (mn ) time when m = Ω(nε ) for any fixed ε ∈ (0,1].

Let τ and σ be two polygonal curves in →., d for any fixed d. Suppose that τ and σ have n and m vertices, respectively, and m≤ n. While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of nc in strongly subquadratic time, for some constant cϵ(0,1). We present a randomized algorithm with running time O(nm0.99log(n/ϵ)) that approximates the Fréchet distance within a factor of 7+ϵ, with a success probability at least 1-1/n6. We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ϵ in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

Let $P$ be a set of at most $n$ points and let $R$ be a set of at most $n$ geometric ranges, such as for example disks or rectangles, where each $p \in P$ has an associated supply $s_{p} > 0$, and each $r \in R$ has an associated demand $d_{r} > 0$. A (many-to-many) matching is a set $\mathcal{A}$ of ordered triples $(p,r,a_{pr}) \in P \times R \times \mathbb{R}_{>0}$ such that $p \in r$ and the $a_{pr}$'s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing $\sum_{(p,r,a_{pr}) \in \mathcal{A}} a_{pr}$. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of $n$ red points $P$ and a set of $n$ blue points $Q$ that minimizes the length of the longest edge. For the $L_\infty$-metric, we can do this in time $O(n^{1+\varepsilon})$ in any fixed dimension, for the $L_2$-metric in the plane in time $O(n^{4/3 + \varepsilon})$, for any $\varepsilon > 0$.

We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let 𝕏dm and 𝕏dk be the spaces of all polygonal curves of m and k vertices in ℝd, respectively. We assume that k ≤ m. Let be the set of ranges in 𝕏dm for all possible metric balls of polygonal curves in 𝕏dk under the Fréchet distance. We prove a nearly optimal bound of O(dk log(km)) on the VC dimension of the range space (𝕏dm, ), improving on the previous O(d2k2 log(dkm)) upper bound and approaching the current Ω(dk log k) lower bound. Our upper bound also holds for the weak Fréchet distance. We also obtain exact solutions that are hitherto unknown for the curve simplification, range searching, nearest neighbor search, and distance oracle problems.

We propose $κ$-approximate nearest neighbor (ANN) data structures for $n$ polygonal curves under the Fréchet distance in $\mathbb{R}^d$, where $κ\in \{1+\varepsilon,3+\varepsilon\}$ and $d \geq 2$. We assume that every input curve has at most $m$ vertices, every query curve has at most $k$ vertices, $k \ll m$, and $k$ is given for preprocessing. The query times are $\tilde{O}(k(mn)^{0.5+\varepsilon}/\varepsilon^d+ k(d/\varepsilon)^{O(dk)})$ for $(1+\varepsilon)$-ANN and $\tilde{O}(k(mn)^{0.5+\varepsilon}/\varepsilon^d)$ for $(3+\varepsilon)$-ANN. The space and expected preprocessing time are $\tilde{O}(k(mnd^d/\varepsilon^d)^{O(k+1/\varepsilon^2)})$ in both cases. In two and three dimensions, we improve the query times to $O(1/\varepsilon)^{O(k)} \cdot \tilde{O}(k)$ for $(1+\varepsilon)$-ANN and $\tilde{O}(k)$ for $(3+\varepsilon)$-ANN. The space and expected preprocessing time improve to $O(mn/\varepsilon)^{O(k)} \cdot \tilde{O}(k)$ in both cases. For ease of presentation, we treat factors in our bounds that depend purely on $d$ as~$O(1)$. The hidden polylog factors in the big-$\tilde{O}$ notation have powers dependent on $d$.

We present new approximation results on curve simplification and clustering under Fréchet distance. Let T = {ti : i ∈ [n]} be polygonal curves in ℝd of m vertices each. Let ℓ be any integer from [m]. We study a generalized curve simplification problem: given error bounds δi > 0 for i ∈ [n], find a curve σ of at most ℓ vertices such that dF (σ, ti) ≤ δi for i ∈ [n]. We present an algorithm that returns a null output or a curve σ of at most ℓ vertices such that dF(σ,τi) < δi + εδmax for i ∈ [n], where δmax = maxi∈[n] δi. If the output is null, there is no curve of at most ℓ vertices within a Frechet distance of δi from τi for i ∈ [n]. The running time is Õ (nO(ℓ) · mO(ℓ2) · (dℓ/ε)O(dℓ). This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve τ to another curve σ, where the vertices of σ can be anywhere in ℝd, so that dF(σ,τ) ≤ (1 + ε)δ and |σ| ≤ (1 + α) · min{|c|: dF(c,τ) ≤ δ} for any given δ > 0 and any fixed α,ε ∈ (0,1). The running time is Õ(mO(1/α) · (d/(αε))O(d/α)). By combining our technique with some previous results in the literature, we obtain an approximation algorithm for (k,ℓ)-median clustering. Given T, it computes a set Σ of k curves, each of ℓ vertices, such that is within a factor 1 + ε of the optimum with probability at least 1 — μ for any given μ, ε ∈ (0,1). The running time is † The full version of the paper can be accessed at https://arxiv.org/abs/2207.07809

We propose a dynamic data structure for the distribution-sensitive point location problem in the plane. Suppose that there is a fixed query distribution within a convex subdivision S , and we are given an oracle that can return in O (1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain S such that each query is answered in O opt (S) ) expected time, where opt ( S ) is the expected time of the best linear decision tree for answering point location queries in S . The space and construction time are O(n log 2 n ), where n is the number of vertices of S . An update of S as a mixed sequence of k edge insertions and deletions takes O(k log 4 n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log 4 n ) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.

We propose a self-improving algorithm for computing Voronoi diagrams under a given convex distance function with constant description complexity. The $n$ input points are drawn from a hidden mixture of product distributions; we are only given an upper bound $m = o(\sqrt{n})$ on the number of distributions in the mixture, and the property that for each distribution, an input instance is drawn from it with a probability of $Ω(1/n)$. For any $\varepsilon \in (0,1)$, after spending $O\bigl(mn\log^{O(1)} (mn) + m^{\varepsilon} n^{1+\varepsilon}\log(mn)\bigr)$ time in a training phase, our algorithm achieves an $O\bigl(\frac{1}{\varepsilon}n\log m + \frac{1}{\varepsilon}n2^{O(\log^* n)} + \frac{1}{\varepsilon}H\bigr)$ expected running time with probability at least $1 - O(1/n)$, where $H$ is the entropy of the distribution of the Voronoi diagram output. The expectation is taken over the input distribution and the randomized decisions of the algorithm. For the Euclidean metric, the expected running time improves to $O\bigl(\frac{1}{\varepsilon}n\log m + \frac{1}{\varepsilon}H\bigr)$.

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots,x_n$ follow some unknown \emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $\mathsf{D}_i$, and the $x_i$'s are drawn independently. After spending $O(n^{1+\varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/\varepsilon)$, where $H \in \{H_\mathrm{S},H_\mathrm{DT}\}$, and $H_\mathrm{S}$ and $H_\mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$'s under the \emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$'s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$'s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$'s are well-behaved. After an $O(\mathrm{poly}(n))$-time training phase, we achieve $O(n + H_\mathrm{S})$ and $O(nα(n) + H_\mathrm{DT})$ expected running times for sorting and DT, respectively, where $α(\cdot)$ is the inverse Ackermann function.

We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in ℝ², and we are given an oracle that can return in O(1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain a convex subdivision S with n vertices such that each query is answered in O(OPT) expected time, where OPT is the minimum expected time of the best linear decision tree for point location in S. The space and construction time are O(n log² n). An update of S as a mixed sequence of k edge insertions and deletions takes O(k log⁵ n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log⁵ n) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.

Ailon et al. (SIAM J Comput 40(2):350–375, 2011 ) proposed a self-improving sorter that tunes its performance to an unknown input distribution in a training phase. The input numbers \(x_1,x_2,\ldots ,x_n\) come from a product distribution, that is, each \(x_i\) is drawn independently from an arbitrary distribution \({{{\mathcal {D}}}}_i\) . We study two relaxations of this requirement. The first extension models hidden classes in the input. We consider the case that numbers in the same class are governed by linear functions of the same hidden random parameter. The second extension considers a hidden mixture of product distributions.

Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most $4$. However, their proof does not give a polynomial-time approximation algorithm. A lot of efforts have been devoted to designing an efficient algorithm whose approximation ratio can match this upper bound for the integrality gap. In ICALP 2018, we present a $(6 + δ)$-approximation algorithm where $δ$ can be any positive constant, and there is still a gap of roughly $2$. In this paper, we narrow the gap significantly by proposing a $(4+δ)$-approximation algorithm where $δ$ can be any positive constant. The approximation ratio is with respect to the optimal value of the configuration LP, and the running time is $\mathit{poly}(m,n)\cdot n^{\mathit{poly}(\frac{1}δ)}$ where $n$ is the number of players and $m$ is the number of resources. We also improve the upper bound for the integrality gap of the configuration LP to $3 + \frac{21}{26} \approx 3.808$.

The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algorithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: roughly 4 for estimation and roughly $6 + 2\sqrt{10}$ for construction. We propose an algorithm that constructs an allocation with value within a factor of $6 + δ$ from the optimum for any constant $δ> 0$. The running time is polynomial in the input size for any constant $δ$ chosen.

We present a self-adjusting point location structure for convex subdivisions. Let n be the number of vertices in a convex subdivision S. Our structure for S uses O(n) space and processes any online query sequence sigma in O(n + OPT) time, where OPT is the minimum time required by any linear decision tree for answering point location queries in S to process sigma. The O(n + OPT) time bound includes the preprocessing time. Our result is a two-dimensional analog of the static optimality property of splay trees. For connected subdivisions, we achieve a processing time of O(|sigma| log log n + n + OPT).

We present an algorithm for surface reconstruction from a point cloud. It runs in O ( n log n ) time, where n is the number of sample points, and this is optimal in the pointer machine model. The only existing O ( n log n )-time algorithm is due to Funke and Ramos, and it uses some sophisticated data structures. The key task is to extract a locally uniform subsample from the input points. Our algorithm is much simpler and it is based on a variant of the standard octree. We built a prototype that runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the sample points absent from the subsample via edge flips. In our experiments with some nonuniform samples, the subsample extraction step is fast and effective, and the prototype gives a 51% to 68% speedup over using Cocone alone. The prototype also runs faster on locally uniform samples.

The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively.

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O ( n (log n )log r ) time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected O ( n sqrt h + 1 log 2 n ) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a nondegenerate polygon in O ( n (log n )log r + r 4/3 + ε ) time for any ε > 0. On degenerate input, our time bound increases to O ( n (log n )log r + r 17/11 + ε ).

Given a time series S = ((x1, y1), (x2, y2), …) and a prescribed error bound ε, the piecewise linear approximation (PLA) problem with max-error guarantees is to construct a piecewise linear function f such that |f(xi)-yi| ≤ ε for all i. In addition, we would like to have an online algorithm that takes the time series as the records arrive in a streaming fashion, and outputs the pieces of f on-the-fly. This problem has applications wherever time series data is being continuously collected, but the data collection device has limited local buffer space and communication bandwidth, so that the data has to be compressed and sent back during the collection process. Prior work addressed two versions of the problem, where either f consists of disjoint segments, or f is required to be a continuous piecewise linear function. In both cases, existing algorithms can produce a function f that has the minimum number of pieces while meeting the prescribed error bound ε. However, we observe that neither minimizes the true representation size of f, i.e., the number of parameters required to represent f. In this paper, we design an online algorithm that generates the optimal PLA in terms of representation size while meeting the prescribed max-error guarantee. Our experiments on many real-world data sets show that our algorithm can reduce the representation size of f by around 15% on average compared with the current best methods, while still requiring O(1) processing time per data record and small space.

Let be a planar subdivision with n vertices. Each face of has a weight from [1, ρ] ∪ {∞}. A path inside a face has cost equal to the product of its length and the face weight. In general, the cost of a path is the sum of the subpath costs in the faces intersected by the path. For any ε ∊ (0, 1), we present a fully polynomial-time approximation scheme that finds a (1 + ε)-approximate shortest path between two given points in in time, where k is the smallest integer such that the sum of the k smallest angles in is at least π. Therefore, our running time can be as small as if there are O(1) small angles and it is in the worst case. Our algorithm relies on a new triangulation refinement method, which produces a triangulation of size O(n + k2) such that no triangle has two angles less than min{π/(2k), π/12}.

Let P be a dense set of points sampled from an m-dimensional compact smooth manifold Σ in ℝd. We show how to construct an implicit function φ : ℝd → ℝd–m from P so that the zero-set Sφ of φ contains a homeomorphic approximation of Σ. The Hausdorff distance between Σ and this homeomorphic approximation is at most ∊τ for any fixed τ < 2. Moreover, for every point × at distance ∊τ or less from Σ, the normal space of Sφ at × makes an O(∊(τ–1)/2) angle with the normal space of Σ at the point nearest to ×. The function φ has local support, which makes local homeomorphic reconstruction possible without a complete sampling.

We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L1 and L∞ shortest paths on a polyhedral surface in O(n2 log4 n) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε)-approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O[EQUATION]. This is the first efficient PTAS for such a general setting of terrain navigation.

We present an approximation algorithm for the shortest descending path problem. Given a source $s$ and a destination $t$ on a terrain, a shortest descending path from $s$ to $t$ is a path of minimum Euclidean length on the terrain subject to the constraint that the height decreases monotonically as we traverse that path from $s$ to $t$. Given any $\varepsilon \in (0,1)$, our algorithm returns in $O(n^4\log (n/\varepsilon))$ time a descending path of length at most $1+\varepsilon$ times the optimum. This is the first algorithm whose running time is polynomial in $n$ and $\log(1/\varepsilon)$ and independent of the terrain geometry.

We present an approximate algorithm for the shortest descending path (SDP) problem. Given a source s and a destination t in a polygonal terrain T, an SDP from s to t is a path in T of minimum Euclidean length subject to the constraint that the height decreases monotonically as we traverse that path from s to t. Given any ε ∊ (0, 1), our algorithm returns in O(n4 log(n/ε)) time a descending path of length at most 1 + ε times the optimum. This is the first algorithm whose running time is polynomial in n and log(1/ε) and independent of the terrain geometry.

We present an algorithm to reconstruct a surface from a dense sample. Given n sample points, it runs in O(n log n) time, which is optimal in the pointer machine model. The only existing O(n log n)-time algorithm due to Funke and Ramos uses some sophisticated data structures for the key task of extracting a locally uniform subsample. Our algorithm is based on a variant of the standard octree, and it is much simpler. We built a prototype, which runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the samples points absent from the subsample via edge flips. The subsample extraction step is very fast and effective. In our experiments with some non-uniform samples, our prototype gives a 51% to 68% speedup from using Cocone alone. Even for locally uniform samples, our prototype is usually much faster.

We present an algorithm to compute an approximate overlap of two convex polytopes P_1 and P_2 in R^3 under rigid motion. Given any epsilon in (0,1/2], our algorithm runs in O(epsilon^{-3}n log^{3.5}n) time with probability 1 - n^{-O(1)} and returns a (1-epsilon)-approximate maximum overlap, provided that the maximum overlap is at least lambda max(|P_1|,|P_2|) for some given constant lambda in (0,1].

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 edge flips in a surface mesh and the maintenance of a deforming surface mesh. If the vertices are dense with respect to the local feature size and the triangles have angles at least a constant, we can flip edges in linear time such that all triangles have almost empty diametric balls. For a planar triangulation with a constant angle lower bound, we can flip it to the Delaunay triangulation in linear time. We combine edge flips and vertex nsertions and deletions in an algorithm to maintain a deforming surface mesh, specified only by a dense sample of n points that move with the surface. Under a reasonable motion model, we can enforce bounded aspect ratios and a small approximation error throughout the deformation. The update takes O(n) time at each time step. Our surface mesh maintenance algorithm also gives a good performance in experiments.

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let $\rho\geqslant1$ be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. Let $\varepsilon$ be any number strictly between 0 and 1. Our data structure returns a $(1+\varepsilon)$ approximation of the shortest path cost from the fixed source to a query destination in $O(\log\frac{\rho n}{\varepsilon})$ time. Afterwards, a $(1+\varepsilon)$-approximate shortest path can be reported in $O(\log n)$ time plus the complexity of the path. The data structure uses $O(\frac{\rho^2n^3}{\varepsilon^2}\log\frac{\rho n}{\varepsilon})$ space and can be built in $O(\frac{\rho^2n^3}{\varepsilon^2}(\log\frac{\rho n}{\varepsilon})^2)$ time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle.

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 present a novel approach to estimate the dimension m of an unknown manifold M ⊂ ℝ with positive reach from a set of point samples P ⊆ M. It works by analyzing the shape of simplices formed by point samples. Suppose that P is drawn from M according to a Poisson process with an unknown parameter λ. Let k be some fixed positive integer. When λ is large enough, we prove that the dimension can be correctly output in O(kd|P|1+1/k) time with probability greater than 1 − 2−-k. We experimented with a practical variant and showed that its performance is competitive with several previous methods.

Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let $\rho\geq 1$ be a real number. Distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any $\varepsilon\in(0,1)$ and for any two points $v_s$ and $v_d$, we give an algorithm that finds a path from $v_s$ to $v_d$ whose cost is at most $(1+\varepsilon)$ times the optimal. Our algorithm runs in $O(\frac{\rho^2\log \rho}{\varepsilon^2}n^3 \log(\frac{\rho n}\varepsilon))$ time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in $[1,\rho]\cup \{\infty\}$, the time bound of our algorithm improves to $O(\frac{\rho\log \rho}{\varepsilon}n^3 \log(\frac{\rho n}\varepsilon))$.

We present a data structure for answering approximate shortest path queries ina planar subdivision from a fixed source. Let ρ ≥ 1 be a real number.Distances in each face of this subdivision are measured by a possiblyasymmetric convex distance function whose unit disk is contained in aconcentric unit Euclidean disk, and contains a concentric Euclidean disk withradius 1/ρ. Different convex distance functions may be used for differentfaces, and obstacles are allowed. Let ε be any number strictly between 0and 1. Our data structure returns a (1+ε)approximation of the shortest path cost from the fixed source to a querydestination in O(logρn/ε) time. Afterwards, a(1+ε)-approximate shortest path can be reported in time linear in itscomplexity. The data structure uses O(ρ2 n4/ε2 log ρn/ε) space and can be built in O((ρ2 n4)/(ε2)(log ρn/ε)2) time. Our time and space bounds do not depend onany geometric parameter of the subdivision such as the minimum angle.

This paper presents an algorithm for sampling and triangulating a generic $C^2$-smooth surface $\Sigma\subset \mathbb{R}^3$ that is input with an implicit equation. The output triangulation is guaranteed to be homeomorphic to $\Sigma$. We also prove that the triangulation has well-shaped triangles, large dihedral angles, and a small size. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely, computations of the intersection points of a line and $\Sigma$, computations of the critical points in a given direction, and computations of certain silhouette points.

We present simple algorithms for detecting the dimension k of a smooth manifold M ⊂ Rd from a set P of point samples, provided that P satisfies a standard sampling condition as in previous results. The best running time so far is O(d2O(k7 log k)) worst-case by Giesen and Wagner after the adaptive neighborhood graph is constructed in O(d|P|2) worst-case time. Given the adaptive neighborhood graph, for any l ≥ 1, our algorithm outputs the true dimension with probability at least 1-2-l in O(2O(k)kd(k + l log d)) expected time. Our experimental results validate the effectiveness of our approach in computing the dimension. A further advantage is that both the algorithm and its analysis can be generalized to the noisy case, in which outliers and a small perturbation of the samples are allowed.

This paper presents an algorithm for sampling and triangulatinga smooth surface Σ ⊂ ℝ3 where the triangulation is homeomorphic to Σ. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely computations of the intersection points of a line with the surface, computations of the critical points of some height functions defined on the surface and its restriction to a plane, and computations of some silhouette points. The algorithm ensures bounded aspect ratio, size optimality, and smoothness of the output triangulation. Unlike previous algorithms, this algorithm does not need to compute the local feature size for generating the sample points which was a major bottleneck. Experiments show the usefulness of the algorithm in remeshing and meshing CAD surfaces that are piecewise smooth.

We present an algorithm to compute a Delaunay mesh conforming to a polyhedron possibly with small input angles. The radius-edge ratio ofmost output tetrahedra are bounded by a constant, except possibly those that are provably close to small angles. Further, the mesh is graded, that is, edge lengths are at least a constant fraction of the local feature sizes at the edge endpoints. Unlike a previous algorithm, this algorithm is simple to implement as it avoids computing local feature sizes and protective zones explicitly. Our experimental results confirm our claims and show that few skinny tetrahedra remain.

We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases.We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra, called slivers, that can occur in such a mesh can be eliminated by the sliver exudation method. This method has been shown to work for periodic point sets, but not with boundaries. Recently a randomized point-placement strategy has been proposed to remove slivers while conforming to a given boundary. In this paper we present a deterministic algorithm for generating a weighted Delaunay mesh which respects the input boundary and has no poor quality tetrahedron including slivers. As in previous work, we assume that no input angle is acute. Our result is achieved by combining the weight pumping method for sliver exudation and the Delaunay refinement method for boundary conformation.

A sliver is a tetrahedon whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional Delaunay triangulations even for well-spaced point sets. We show that, if the Delaunay triangulation has the ratio property introduced in Miller et al. [1995], then there is an assignment of weights so the weighted Delaunay traingulation contains no slivers. We also give an algorithm to compute such a weight assignment.

A sliver is a tetrahedron whose four vertices lie close to a plane and whose projection to that plane is a convex quadrilateral with no short edge. Slivers are notoriously common in 3-dimensional Delaunay triangulations even for well-spaced point sets. We show that if the Delaunay triangulation has the ratio property introduced in [15] then there is an assignment of weights so the weighted Delaunay triangulation contains no slivers. We also give an algorithm to compute such a weight assignment.

A new hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have maximum degree three. Using this hierarchy, circular ray shooting queries in a simple polygon can be answered in O(log* n) query time and O(nlogn) space. If the radius of the circle is fixed, the query time can be improved to O(logn) and the space to O(n). The decomposition is also applied to three other circular arc query problems: shortest directed arc, arc bending, and arc pushing. Using these queries, the largest empty lune determined by two query points in a simple polygon can be computed in O(log3 n) time, while the circular visibility region of a query point in a simple polygon can be reported in time O(m log3 n), where m is the output size.

Shape deformation refers to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing, and visualizing deformations between two shapes in R2. The deformation is generated automatically without any user intervention or specification of feature correspondences. A unique property of the tool is the explicit availability of the two-dimensional shape space, which can be used for designing the deformation either automatically by following constraints and objectives or manually by drawing deformation paths.

In casting, liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We consider the case where the cast consists of two parts and address the following problems. (1) Given a cast for an object and a direction , can the cast be partitioned into two parts such that the parts can be removed in directions and - , respectively, without colliding with the object or the other cast part? (2) How can one find a direction such that the above cast partitioning can be done? We give necessary and sufficient conditions for both problems, as well as algorithms to decide them for polyhedral objects. We also give some evidence that the case where the cast parts need not be removed in opposite directions is considerably harder.

Given a set S of n points in the plane, a triangulation is a maximal set of non-intersecting edges connecting the points in S. The weight of the triangulation is the sum of the lengths of the edges. The complexity of computing the minimum weight triangulation is currently unresolved. In this paper, we show that for β > 1/sin κ, the β-skeleton of S is a subgraph of a minimum weight triangulation of S, where κ = tan-1(3/√2√3) ≈ π/3.1. There exists a four point example such that the β-skeleton for β < 1/sin(π/3) is not a subgraph of the minimum weight triangulation.

Many fault-detection problems fall into the following model: There is a set of n items, some of which are defective. The goal is to identify the defective items by using the minimum number of tests. Each test is on a subset of items and tells whether the subset contains a defective item or not. Let $M_\alpha (d,n)(M_\alpha (d|n))$ denote the maximum number of tests for an algorithm $\alpha $ to identify d defectives from a set of n items provided that d, the number of defective items, is known (unknown) before the testing. Let $M(d,n) = \min _\alpha M_\alpha (d,n)$. An algorithm a is called a competitive algorithm if there exist constants c and a such that for all $n > d > 0,M_\alpha (d|n) \leqslant cM(d,n) + a$. This paper confirms a recent conjecture that there exists a bisecting algorithm A such that $M_A (d|n) \leqslant 2M(d,n) + 1$. Also, an algorithm B such that $M_B (d|n) \leqslant 1.65M(d,n) + 10$ is presented.

In this paper, we consider the problem of determining the smallest clock period for a combinational circuit. By considering both the long and short paths, we derive three independent bounds on the clock period. The first bound is the difference between the longest path delay and the shortest path delay. The other two take the functionality of the circuit into consideration and, therefore, are usually smaller than the first one. To bring in the functionality of the circuit, we make use of a new class of paths-called the shortest destabilizing paths-as well as the longest sensitizable paths. We also show that considering both the longest sensitizable path and the shortest destabilizing path together does not always give a valid bound. The bounds on the clock period can be alternatively viewed as optimization objectives. At the physical level, the complexity of optimization very much depends on the number of long and short paths present and the number of gates shared by them. We conducted preliminary experiments to study this.>

We formulate the performance oriented minimum rectilinear Steiner tree problem (POMRST) which is useful in the case of net connection high performance circuits. Since the POMRST problem is NP-hard, we provide an effective heuristic for it. When we apply our POMRST heuristic to solve the rectilinear Steiner tree problem, our experimental results compare favorably with the existing techniques cited in [11]. In the context of the POMRST problem, our experimental results indicate that a small increase in the total interconnection length can greatly enhance the circuit performance. A related but less general problem has been addressed in [1].

We study the problem of choosing gate implementations to reduce circuit area while retaining the circuit performance. To incorporate timing analysis into area reduction, we propose to utilize the information provided by a sensitization criterion in computing the slacks of the gates. Not all sensitization criteria can be adopted in our approach. Some conditions were imposed to define a class of sensitization criteria which can guarantee that the circuit performance will be preserved. A greedy area reduction heuristic is proposed, and then an improved version of the Brand-Iyengar and the static sensitization criteria are plugged into the heuristic to obtain results for comparison (D. Brand, V. Iyengar, 1986).>

Three algorithms to join two compacted cells by using a combination of stretching and river routing are developed. Each of these obtains the minimum area joining. One algorithm obtains a minimum area joining that also minimizes the length of the longest wire. Another obtains a minimum area joining that has the least possible total wire length. The simplest of the algorithms guarantees only a minimum are joining. All algorithms have a low-order polynomial complexity. Experimental results indicate that the algorithms obtain joinings that are significantly superior to those obtained using the heuristic of G. Cheng and A. Despain (1989).>

A point location scheme is presented for a dynamic planar subdivision whose underlying graph is only required to be connected. The operations supported include: reporting the name of the region containing a query point, inserting/deleting an edge, and inserting/deleting/moving a degree-2 vertex. The scheme uses $O(n)$ space, has a worst-case query time of $O(\log ^2 n)$, and a worst-case update time of $O(\log n)$, where n is the number of vertices currently in the subdivision. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in $O(k\log (n + k))$ (respectively, $O(k\log n)$) time in worst-case. The scheme outperforms the solutions given in works by Fries, Mehlhorn, and Naeher and by Overmars and also handles more general subdivisions than the schemes given in works by Preparata and Tamassia. The result is based on a new solution to a dynamic visibility problem for a set of line segments in the plane that are nonintersecting, except possibly at endpoints. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to $O(\log ^2 n\log \log n + k)$ time (or $O(\log n\log \log n + k)$ time for an alternative model of input), but at the expense of increasing the other time bounds slightly. Additional results include a generalization to subdivisions consisting of algebraic segments of bounded degree and a persistent scheme that allows point location queries in the past and updates in the present.

A point location scheme is presented for an n-vertex dynamic planar subdivision whose underlying graph is only required to be connected. The scheme uses O(n) space and yields an O(log/sup 2/n) query time and an O(log n) update time. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in O(k log(n+k)) (respectively, O(k log n)) time. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to O(log/sup 2/n log log n+k) time (or O(log n log log n+k) time for an alternative model of input), but at the expense of increasing the other time bounds slightly. All bounds are worst case. Additional results include a generalization to planar subdivisions consisting of algebraic segments of bounded degree and a persistent scheme for planar point location.>