Search

No abstract received. [ABSTRACT FROM AUTHOR]

The Fréchet distance is a well studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown to be optimal assuming the Strong Exponential Time Hypothesis (SETH) [Bringmann, FOCS'14]. To overcome the worst-case quadratic time barrier, restricted classes of curves have been studied that attempt to capture realistic input curves. The most popular such class are -packed curves, for which the Fréchet distance has a -approximation in time [Driemel et al., DCG'12]. In dimension this cannot be improved to for any unless SETH fails [Bringmann, FOCS'14]. In this paper, exploiting properties that prevent stronger lower bounds, we present an improved algorithm with time complexity . This improves upon the algorithm by Driemel et al. for any . Moreover, our algorithm's dependence on , and is optimal in high dimensions apart from lower order factors, unless SETH fails. Our main new ingredients are as follows: For filling the classical free-space diagram we project short subcurves onto a line, which yields one-dimensional separated curves with roughly the same pairwise distances between vertices. Then we tackle this special case in near-linear time by carefully extending a greedy algorithm for the Fréchet distance of one-dimensional separated curves. [ABSTRACT FROM AUTHOR]

Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let P and Q be two polygonal curves in ℝ d with n and m vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in O ((n + m) log (n + m)) time, (3) a linear-time d -approximation algorithm, and (4) a data structure that supports O (m log 2 n) -time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to construct non-circular shapes via pure geometry which are indistinguishable from a perfect circle according to the results of applying so-called V-block tests. We mean that the geometry of the curve is such that the test will, from a purely theoretical point of view, apparently show no departure from roundness whatsoever. In doing so, we call into question the theoretical basis for these practical V-block tests. [ABSTRACT FROM AUTHOR]

The Hausdorff distance between two sets of curves is a measure for the similarity of these objects and therefore an interesting feature in shape recognition. If the curves are algebraic computing the Hausdorff distance involves computing the intersection points of the Voronoi edges of the one set with the curves in the other. Since computing the Voronoi diagram of curves is quite difficult we characterize those points algebraically and compute them using the computer algebra system SYNAPS. This paper describes in detail which points have to be considered, by what algebraic equations they are characterized, and how they actually are computed. [ABSTRACT FROM AUTHOR]

We present the first algorithm for constructing abstract Voronoi diagrams from bisectors that are unbounded or closed Jordan curves. It runs in expected many steps and space, where is the number of sites, denotes the average number of faces (connected components) per Voronoi region in any diagram of a subset of sites, and is the maximum number of intersection points between any two related bisectors. [ABSTRACT FROM AUTHOR]

This article presents an algorithm to construct constrained Delaunay tetrahedralizations of geometric domains bounded by piecewise smooth surfaces. Meshes are built from the bottom-up by first discretizing the boundary curves and then by sampling the smooth surfaces. The sampling procedure refines the Delaunay triangulation restricted to these surfaces, targeting topological violations and poor quality triangles. Unlike previously published algorithms adopting a similar approach, we propose to sample each smooth surface patch independently. This obviates the need for a boundary protection scheme around small dihedral angles in the input and can also lead to coarser constraining triangulations. Starting from a Delaunay tetrahedralization of the point samples, a combination of mesh reconfigurations and vertex insertions is then used to obtain a tetrahedralization constrained to the boundary surfaces. The algorithm is designed to produce tetrahedralizations that can be used in conjunction with a Delaunay refinement algorithm implemented on a Bowyer-Watson framework. [ABSTRACT FROM AUTHOR]

Homeomorphisms between curves and between surfaces are fundamental to many applications of 3D modeling, graphics, and animation. They define how to map a texture from one object to another, how to morph between two shapes, and how to measure the discrepancy between shapes or the variability in a class of shapes. Previously proposed maps between two surfaces, S and S′, suffer from two drawbacks: (1) it is difficult to formally define a relation between S and S′ which guarantees that the map will be bijective and (2) mapping a point x of S to a point x′ of S′ and then mapping x′ back to S does in general not yield x, making the map asymmetric. We propose a new map, called ball-map, that is symmetric. We define simple and precise conditions for the ball-map to be a homeomorphism. We show that these conditions apply when the minimum feature size of each surface exceeds their Hausdorff distance. The ball-map, BMS,S′, between two such manifolds, S and S′, maps each point x of S to a point x′ = BMs,s′(x) of S′. BMS′,S is the inverse of BMS,S′, hence BM is symmetric. We also show that, when S and S′ are Ck (n - 1)-manifolds in ℝn, BMS,S′ is a Ck-1 diffeomorphism and defines a Ck-1 ambient isotopy that smoothly morphs between S to S′. In practice, the ball-map yields an excellent map for transferring parameterizations and textures between ball compatible curves or surfaces. Furthermore, it may be used to define a morph, during which each point x of S travels to the corresponding point x′ of S′ along a broken line that is normal to S at x and to S′ at x′. [ABSTRACT FROM AUTHOR]

We present an algorithm for approximating multiple closed polygons in a tangent-continuous manner with circular biarcs. The approximation curves are guaranteed to lie within a user-specified tolerance of the original input. If requested, our algorithm can also ensure that the input is within a user-specified tolerance of the approximation curves. These tolerances can be either symmetric, asymmetric, one-sided, or even one-sided and completely disconnected from the inputs. Our algorithm makes use of Voronoi diagrams to build disjoint and continuous tolerance bands for every polygon of the input. In a second step the approximation curves are fitted into the tolerance bands. Our algorithm has a worst-case complexity of O(n log n) for an n-vertex input. Extensive experiments with synthetic and real-world data sets show that our algorithm generates approximation curves with significantly fewer approximation primitives than previously proposed algorithms. This difference becomes more prominent the larger the tolerance threshold is or the more severe the noise in the input is. In particular, no heuristic is needed for smoothing noisy input prior to the actual approximation. Rather, our approximation algorithm can be used to smooth out noise in a reliable manner. [ABSTRACT FROM AUTHOR]