Search

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]

To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve dividing a task into a number of smaller tasks, while optimizing a specific objective function. In this paper we consider the problem of partitioning a given set S of n points in the plane into k subsets, S[sub 1], …, S[sub k], such that max[sub 1≤i≤k] MST(S[sub i]) is minimized. Variants of this problem arise in applications from the shipbuilding industry. We show that this problem is NP-hard, and we also present an approximation algorithm for the problem, in the case when k is a fixed constant. The approximation algorithm runs in time O(n log n) and produces a partition that is within a factor (4/3 + ε) of the optimal if k = 2, and a factor (2 + ε) otherwise. [ABSTRACT FROM AUTHOR]

This paper studies the influence of the definition of neighborhoods and methods used for creating point connectivity on topological analysis of scalar functions. It is assumed that a scalar function is known only at a finite set of points with associated function values. In order to utilize topological approaches to analyze the scalar-valued point set, it is necessary to choose point neighborhoods and, usually, point connectivity to meaningfully determine critical-point behavior for the point set. Two distances are used to measure the difference in topology when different point neighborhoods and means to define connectivity are used: (i) the bottleneck distance for persistence diagrams and (ii) the distance between merge trees. Usually, these distances define how different scalar functions are with respect to their topology. These measures, when properly adapted to point sets coupled with a definition of neighborhood and connectivity, make it possible to understand how topological characteristics depend on connectivity. Noise is another aspect considered. Five types of neighborhoods and connectivity are discussed: (i) the Delaunay triangulation; (ii) the relative neighborhood graph; (iii) the Gabriel graph; (iv) the -nearest-neighbor (KNN) neighborhood; and (v) the Vietoris-Rips complex. It is discussed in detail how topological characterizations depend on the chosen connectivity. [ABSTRACT FROM AUTHOR]

We consider the following packing problem. Let α be a fixed real in (0, 1]. We are given a bounding rectangle ρ and a set $\cal R$ of n possibly intersecting unit disks whose centers lie in ρ. The task is to pack a set $\cal B$ of m disjoint disks of radius α into ρ such that no disk in B intersects a disk in $\cal R$, where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for α = 2/3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for α = 2/3 and have shown that the problem cannot be solved in polynomial time for any α > 13/14 unless ${\cal P}={\cal NP}$. [ABSTRACT FROM AUTHOR]

In this paper, we consider constant factor approximation algorithms for a variant of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points in P to pierce the unit disks centered at all the points in P. We first propose a very simple algorithm that produces 12-approximation result in O(n log n) time. Next, we improve the approximation factor to 4 and then to 3. The worst case running time of these algorithms are O(n8 log n) and O(n15 log n) respectively. Apart from the space required for storing the input, the extra work-space requirement for each of these algorithms is O(1). Finally, we propose a PTAS for the same problem. Given a positive integer k, it can produce a solution with performance ratio (1+1/k)2 in nO(k) time. [ABSTRACT FROM AUTHOR]

Given a real ∊ > 0, an integer g ≥ 0 and a set of points in the plane, we study the problem of computing a piecewise linear functional curve with minimum number of line segments to approximate all points after removing g outliers such that the approximation error is at most ∊. We give an improved algorithm over the previous work. The algorithm is based on two dynamic data structures developed in this paper for the simplicial thickness queries, which are of independent interest. For a set S of simplices in the d-dimensional space ℝd (d ≥ 2 is a constant), the simplicial thickness of a point p is defined as the number of simplices in S that contain p. Given a set P of n points in ℝd, we develop two dynamic data structures to support the following operations. (1) Simplex insertion: Insert a simplex into S. (2) Simplex deletion: Delete a simplex from S. (3) Simplicial thickness query: Given a query simplex σ, compute the minimum simplicial thickness among all points in σ∩P. The first data structure is constructed in O(n1+δ) time, for any constant δ > 0, and can support each operation in O(n1-1/d) time; the second one is con-structed in O(n n) time and can support each operation in O(n1-1/d ( n)O(1)) time. Both data structures use O(n). space. These data structures may find other applications as well. [ABSTRACT FROM AUTHOR]

The complexity status of the minimum r-star cover problem for orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomially tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, since their algorithm has Õ(n17)-time complexity, where Õ(·) hides a polylogarithmic factor, and thus it is not practical, in this paper we present a linear-time 3-approximation algorithm. Our approach is based upon the novel partition of an orthogonal polygon into so-called o-star-shaped orthogonal polygons. [ABSTRACT FROM AUTHOR]

Given a set T of n points in ℝ2, a Manhattan network on T is a graph G = (V,E) with the property that all the edges in E are vertical or horizontal line segments connecting points in V ⊇ T and for all p, q ∈ T, the graph contains a path having the length exactly L1 distance between p and q. The Minimum Manhattan Network problem is to find a Manhattan network of minimum length, i.e. minimizing the total length of the line segments of the network. In this paper we present a 2-approximation algorithm with time complexity O(n log n), which improves over a recent combinatorial 2-approximation algorithm with running time O(n2). Moreover, compared with other 2-approximation algorithms using linear programming or dynamic programming techniques, we show that a greedy strategy suffices to obtain a 2-approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study several instances of the alignedk-center problem where the goal is, given a set of points S in the plane and a parameter k ⩾ 1, to find k disks with centers on a line ℓ such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line ℓ is given in advance; we can solve this problem in time O(n log2 n). In the case where only the direction of ℓ is fixed, we give an O(n2log2 n)-time algorithm. When ℓ is an arbitrary line, we give a randomized algorithm with expected running time O(n4log2 n). Then we present (1+ε)-approximation algorithms for these three problems. When we denote T(k, ε) = (k/ε2+(k/ε) log k) log(1/ε), these algorithms run in O(n log k + T(k, ε)) time, O(n log k + T(k, ε)/ε) time, and O(n log k + T(k, ε)/ε2) time, respectively. For k = O(n1/3/log n), we also give randomized algorithms with expected running times O(n + (k/ε2) log(1/ε)), O(n+(k/ε3) log(1/ε)), and O(n + (k/ε4) log(1/ε)), respectively. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

A planar polyomino of size n is an edge-connected set of n squares on a rectangular two-dimensional lattice. Similarly, a d-dimensional polycube (for d ≥ 2) of size n is a connected set of n hypercubes on an orthogonal d-dimensional lattice, where two hypercubes are neighbors if they share a (d - 1)-dimensional face. There are also two-dimensional polyominoes that lie on a triangular or hexagonal lattice. In this paper we describe a generalization of Redelmeier's algorithm for counting two-dimensional rectangular polyominoes, which counts all the above types of polyominoes. For example, our program computed the number of distinct three-dimensional polycubes of size 18. To the best of our knowledge, this is the first tabulation of this value. [ABSTRACT FROM AUTHOR]

The medial axis of a shape is known to carry a lot of information about the shape. In particular, a recent result of Lieutier establishes that every bounded open subset of ℝn has the same homotopy type as its medial axis. In this paper we provide an algorithm that computes a structure we call the core for the approximation of the medial axis of a shape with smooth boundary from a discrete sample of its boundary. The core is a piecewise linear cell complex that is guaranteed to capture the topology of the medial axis of the shape provided the sample of its boundary is sufficiently dense but not necessarily uniform. We also present a natural method for augmenting the core in order to extend it geometrically while maintaining the topological guarantees. The definition of the core and its extension are based on the steepest ascent flow map that results from the distance function induced by the sample point set. We also provide a geometric guarantee on the closeness of the core and the actual medial axis. [ABSTRACT FROM AUTHOR]

We study the General Position Subset Selection problem: Given a set of points in the plane, find a maximum-cardinality subset of points in general position. We prove that General Position Subset Selection is NP-hard, APX-hard, and present several fixed-parameter tractability results for the problem as well as a subexponential running time lower bound based on the Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]

We present an embedding and search reduction which allow us to build the first data structure for the nearest neighbor search among small point sets with respect to the directed Hausdorff distance under translation. The search structure is non-heuristic in the sense that the quality of the results, the performance, and the space bound are guaranteed. Let n denote the number of point sets in the data base, s the maximal size of a point set, and d the dimension of the points. The nearest neighbor of a query point set under the translation invariant directed Hausdorff distance can be approximated by one or several nearest neighbor searches for single points in the Euclidean embedding space ℝd(s-1). The approximation factor is $\sqrt {{{ds} \mathord{\left/ {\vphantom {{ds} 2}} \right. \kern-\nulldelimiterspace} 2}} $ in case of even s and $\sqrt {{{d\left( {{{s\, - \,1} \mathord{\left/ {\vphantom {{s\, - \,1} s}} \right. \kern-\nulldelimiterspace} s}} \right)} \mathord{\left/ {\vphantom {{d\left( {{{s\, - \,1} \mathord{\left/ {\vphantom {{s\, - \,1} s}} \right. \kern-\nulldelimiterspace} s}} \right)} 2}} \right. \kern-\nulldelimiterspace} 2}} $ when s is odd. Depending on the direction of the Hausdorff distance either the number of queries or the space requirements are exponential in s. Furthermore it is shown how to find the exact nearest neighbor under the directed Hausdorff distance without transformation of the point sets within some weaker time and space bounds. [ABSTRACT FROM AUTHOR]

Significant progress has been accomplished during the past decades about geometric constraint solving, in particular thanks to its applications in industrial fields like CAD and robotics. In order to tackle problems of industrial size, many solving methods use, as a preprocessing, decomposition techniques that transform a large geometric constraint system into a set of smaller ones. In this paper, we propose a survey of the decomposition techniques for geometric constraint problems . We classify them into four categories according to their modus operandi, establishing some similarities between methods that are traditionally separated. We summarize the advantages and limitations of the different approaches, and point out key issues for meeting industrial requirements such as generality and reliability. [ABSTRACT FROM AUTHOR]

Data clustering is a fundamental problem arising in many practical applications. In this paper, we present new geometric approximation and exact algorithms for the density-based data clustering problem in d-dimensional space ℝd (for any constant integer d ≥ 2). Previously known algorithms for this problem are efficient only when the specified range around each input point, called the δ-neighborhood, contains on average a constant number of input points. Different distributions of the input data points have significant impact on the efficiency of these algorithms. In the worst case when the data points are highly clustered, these algorithms run in quadratic time, although such situations might not occur very frequently on real data. By using computational geometry techniques, we develop faster approximation and exact algorithms for the density-based data clustering problem in ℝd. In particular, our approximation algorithm based on the ∊-fuzzy distance function takes O(n log n) time for any given fixed value ∊>0, and our exact algorithms take sub-quadratic time. The running times and output quality of our algorithms do not depend on any particular data distribution. We believe that our fast approximation algorithm is of considerable practical importance, while our sub-quadratic exact algorithms are more of theoretical interest. We implemented our approximation algorithm and the experimental results show that our approximation algorithm is efficient on arbitrary input point sets. [ABSTRACT FROM AUTHOR]

In this paper, we study a 3D geometric problem originated from computing neural maps in the computational biology community: Given a set S of n points in 3D, compute k cylindrical segments (with different radii, orientations, lengths and no segment penetrates another) enclosing S such that the sum of their radii is minimized. There is no known result in this direction except when k=1. The general problem is strongly NP-hard and we obtain a polynomial time approximation scheme (PTAS) for any fixed k>1 in O(n3k-2/δ4k-3) time by returning k cylindrical segments with sum of radii at most (1+δ) of the corresponding optimal value, if exist. Our PTAS is built upon a simple (though slower) approximation algorithm for the case when k=1. [ABSTRACT FROM AUTHOR]

In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n ∊-separated segments in two dimensional space. Our results are based on an interesting combinatorial result which bounds the total number of entry points in an optimal TSP tour and a generalization of Arora's technique5 for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n2(log n)O(1/∊2)) time to compute a (1+∊)-approximation with probability ≥l/2, and can be derandomized with an additional factor of O(n2). [ABSTRACT FROM AUTHOR]

In this paper we propose and study two practical variations of the map labeling problem: Given a set S of n distinct (point) sites in the plane, label each site with: (1) a pair of non-intersecting squares of maximum possible size, (2) a pair of non-intersecting circles of maximum possible size (all the squares and circles are topologically open and are of uniform size). Almost nothing has been done before in this aspect, i.e., multi-label map labeling. We obtain constant-factor approximation algorithms for these problems. We also study bicriteria approximation schemes for these problems under a mild condition. [ABSTRACT FROM AUTHOR]

A visibility relation can be viewed as a graph: the uncountable graph of a visibility relationship between points in a polygon P is called the point visibility graph (PVG) of P. In this paper we explore the use of perfect graphs to characterize tractable subproblems of visibility problems. Our main result is a characterization of which polygons are guaranteed to have weakly triangulated PVGs, under a generalized notion of visibility called O-visibility. Let O denote a set of line orientations. A connected point set P is called O-convex if the intersection of P with any line with orientation in O is connected. Two points in a polygon are said to be O-visible if there is an O-convex path between them inside the polygon. Let O[sup ⊥] denote the set of orientations perpendicular to orientations in O. Let O' ⊆ O[sup ⊥] be the set of orientations θ such that a "reflex" local maximum in the boundary of P exists with respect to θ. Our characterization of which polygons have weakly-triangulated PVGs is based on restricting the cardinality and span of O'. This characterization allows us to exhibit a class of polygons admitting a polynomial algorithm for O-convex cover. [ABSTRACT FROM AUTHOR]

Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given red points and blue points in the plane, we want to construct a perfect matching between red and blue points that minimizes the length of the longest edge, while imposing a constraint that no two edges may cross each other. We show that the problem cannot be approximately solved within a factor less than 1:277 in polynomial time unless . We give simple dynamic programming algorithms that solve our problem in two special cases, namely (1) the case where the red and blue points form the vertices of a convex polygon and (2) the case where the red points are collinear and the blue points lie to one side of the line through the red points. [ABSTRACT FROM AUTHOR]

In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set of unit disks in . We first present a simple time 5-factor approximation algorithm for this problem, where is the size of the output. The best known 4-factor and 3-factor approximation algorithms for the same problem run in time and respectively [M. De, G. K. Das, P. Carmi and S. C. Nandy, Approximation algorithms for a variant of discrete piercing set problem for unit disks, Int. J. of Computational Geometry and Appl., 22(6):461-477, 2013]. We show that the time complexity of the in-place 4-factor approximation algorithm for this problem can be improved to . A minor modification of this algorithm produces a -factor approximation algorithm in time. The same techniques can be applied to have a 3-factor and a -factor approximation algorithms in time and respectively. Finally, we propose a very important shifting lemma, which is of independent interest, and it helps to present -factor approximation algorithm for the same problem. It also helps to improve the time complexity of the proposed PTAS for the problem. [ABSTRACT FROM AUTHOR]

Motivated by Leinster-Cobbold measures of biodiversity, the notion of the spread of a finite metric space is introduced. This is related to Leinster's magnitude of a metric space. Spread is generalized to infinite metric spaces equipped with a measure and is calculated for spheres and straight lines. For Riemannian manifolds the spread is related to the volume and total scalar curvature. A notion of scale-dependent dimension is introduced and seen for approximations to certain fractals to be numerically close to the Minkowski dimension of the original fractals. [ABSTRACT FROM AUTHOR]

We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of δ-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged. [ABSTRACT FROM AUTHOR]

A path P between two points s and t in a polygonal subdivision with obstacles and weighted regions defines a class of paths that can be deformed to P without passing over any obstacle. We present the first algorithm that, given P and a relative error tolerance ε ϵ (0, 1), computes a path from this class with cost at most 1 + ε times the optimum. The running time is , where k is the number of segments in P and h and n are the numbers of obstacles and vertices in , respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2O(d2)m2n2log2(mn) the minimum Fréchet distance between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log3(mn) + (m2+n2)log (mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L∞ distance, we give an O(dmn (dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the maximum Fréchet distance, as well as the minimum and maximum Fréchet distance under translation. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size). [ABSTRACT FROM AUTHOR]

Determining the best shape to fit a set of points is a fundamental problem in many areas of computer science. We present an algorithm to approximate the k-flat that best fits a set of n points with n - m outliers. This problem generalizes the smallest m-enclosing ball, infinite cylinder, and slab. Our algorithm gives an arbitrary constant factor approximation in O(nk+2/m) time, regardless of the dimension of the point set. While our upper bound nearly matches the lower bound, the algorithm may not be feasible for large values of k. Fortunately, for some practical sets of inliers, we reduce the running time to O(nk+2/mk+1), which is linear when m = Ω(n). [ABSTRACT FROM AUTHOR]

A curvature-based algorithm to simplify a polygonal curve is described, together with its implementation. The so-called SimpliPoly algorithm uses Bézier curves to approximate pieces of the input curve, and assign curvature estimates to vertices of the input polyline from curvature values computed for the Bézier approximations. The authors' implementation of SimpliPoly is interactive and available freely on-line. Additionally, a third-party implementation of SimpliPoly as a plug-in for the GNU Blender 3D modeling software is available. Empirical comparisons indicate that SimpliPoly performs as well as the widely-used Douglas-Peucker algorithm in most situations, and significantly better, because it is curvature-driven, in applications where it is necessary to preserve local features. [ABSTRACT FROM AUTHOR]

A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. Although a shortest path on a terrain unfolds to a straight line, a shortest descending path (SDP) does not. We give a full characterization of the bend angles of an SDP, showing that they follow a generalized form of Snell's law of refraction of light. The complexity of finding SDPs is open-only approximation algorithms are known. We reduce the SDP problem to the problem of finding an SDP through a given sequence of faces. We give polynomial time algorithms for SDPs on two special classes of terrains, but argue that the general case will be difficult. [ABSTRACT FROM AUTHOR]

We study the problem of guarding an orthogonal art gallery with security cameras sliding back and forth along straight tracks. We show that if only vertical (alternatively, horizontal) tracks are allowed, then a solution minimizing the number of tracks can be found in polynomial time, and if both orientations are allowed, then a 2-approximation can be found in polynomial time for x-monotone galleries. [ABSTRACT FROM AUTHOR]

Boundary approximation of planar shapes by circular arcs has quantitative and qualitative advantages compared to using straight-line segments. We demonstrate this by way of three basic and frequent computations on shapes - convex hull, decomposition, and medial axis. In particular, we propose a novel medial axis algorithm that beats existing methods in simplicity and practicality, and at the same time guarantees convergence to the medial axis of the original shape. [ABSTRACT FROM AUTHOR]

We present polynomial time results for computing a minimum separation between two regions in a planar weighted subdivision. Our results are based on a (more general) theorem that characterizes a class of functions for which optimal solutions arise on the boundary of the feasible domain. A direct consequence of this theorem is that a minimum separation goes through a vertex of the weighted subdivision. We also consider extensions and present results for the 3-D case and for a more general case of the 2-D separation problem, in which the separation (link) has associated an ϵ-width. Our results are the first nontrivial upper bounds for these problems. We also discuss simple approximation algorithms for the 2-D case and present a prune-and-search approach that can be used with either the continuous or the approximate solutions to speed up the computation. We have implemented a variant of the two region minimum separation algorithm based on the prune-and-search scheme. [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]

Given A-spline curves and A-patch surfaces that are implicitly defined on triangles and tetrahedra, we determine their NURBS representations. We provide a trimmed NURBS form for A-spline curves and a parametric tensor-product NURBS form for A-patch surfaces. We concentrate on cubic A-patches, providing a C¹-continuous surface that interpolates a given triangulation together with surface normals at the vertices. In many cases we can generate cubic trimming curves that are rationally parametrizable on the triangular faces of the tetrahedra; for the remaining faces we resort to using quadratic curves, which are always rationally parametrizable, to approximate the cubic trimming curves. [ABSTRACT FROM AUTHOR]