Search

Chvátal and Klincsek (1980) gave an O (n 3) -time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set P of n points in the plane. This paper examines a generalization of the problem, the Bottleneck Convex Subsets problem: given a set P of n points in the plane and a positive integer k , select k pairwise disjoint convex subsets of P such that the cardinality of the smallest subset is maximized. Equivalently, a solution maximizes the cardinality of k mutually disjoint convex subsets of P of equal cardinality. We give an algorithm that solves the problem exactly, with running time polynomial in n when k is fixed. We then show the problem to be NP-hard when k is an arbitrary input parameter, even for points in general position. Finally, we give a fixed-parameter tractable algorithm parameterized in terms of the number of points strictly interior to the convex hull. [ABSTRACT FROM AUTHOR]

Given a set S of n points, a weight function w to associate a non-negative weight to each point in S , a positive integer k ≥ 1 , and a real number > 0 , we present algorithms for computing a spanner network G (S , E) for the metric space (S , d w) induced by the weighted points in S. The weighted distance function d w on the set S of points is defined as follows: for any p , q ∈ S , d w (p , q) is equal to w (p) + d π (p , q) + w (q) if p ≠ q , otherwise, d w (p , q) is 0. Here, d π (p , q) is the Euclidean distance between p and q if points in S are in ℝ d , otherwise, it is the geodesic (Euclidean) distance between p and q. The following are our results: (1) When the weighted points in S are located in ℝ d , we compute a k -vertex fault-tolerant (4 +) -spanner network of size O (k n 2 ). (2) When the weighted points in S are located in the relative interior of the free space of a polygonal domain , we detail an algorithm to compute a k -vertex fault-tolerant (4 +) -spanner network with O (k n h + 1 2 lg n) edges. Here, h is the number of simple polygonal holes in . (3) When the weighted points in S are located on a polyhedral terrain , we propose an algorithm to compute a k -vertex fault-tolerant (4 +) -spanner network, and the number of edges in this network is O (k n 2 lg n). [ABSTRACT FROM AUTHOR]

We present new results on two types of guarding problems for polygons. For the first problem, we present an optimal linear time algorithm for computing a smallest set of points that guard a given shortest path in a simple polygon having n edges. We also prove that in polygons with holes, there is a constant c > 0 such that no polynomial-time algorithm can solve the problem within an approximation factor of c log n , unless P=NP. For the second problem, we present a (k + h) -FPT algorithm for computing a shortest tour that sees k specified points in a polygon with h holes. We also present a k -FPT approximation algorithm for this problem having approximation factor 2 . In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of c log n , for some constant c > 0 , unless P  = NP. [ABSTRACT FROM AUTHOR]

The Hausdorff distance is a measure of (dis-)similarity between two sets which is widely used in various applications. Most of the applied literature is devoted to the computation for sets consisting of a finite number of points. This has applications, for instance, in image processing. However, we would like to apply the Hausdorff distance to control and evaluate optimisation methods in level-set based shape optimisation. In this context, the involved sets are not finite point sets but characterised by level-set or signed distance functions. This paper discusses the computation of the Hausdorff distance between two such sets. We recall fundamental properties of the Hausdorff distance, including a characterisation in terms of distance functions. In numerical applications, this result gives at least an exact lower bound on the Hausdorff distance. We also derive an upper bound, and consequently a precise error estimate. By giving an example, we show that our error estimate cannot be further improved for a general situation. On the other hand, we also show that much better accuracy can be expected for non-pathological situations that are more likely to occur in practice. The resulting error estimate can be improved even further if one assumes that the grid is rotated randomly with respect to the involved sets. [ABSTRACT FROM AUTHOR]

A planar point set is in convex position precisely when it has a convex polygonization, that is, a polygonization with maximum interior angle measure at most π. We can thus talk about the convexity of a set of points in terms of its min-max interior angle measure. The main result presented here is a nontrivial upper bound of the min-max value in terms of the number of points in the set. Motivated by a particular construction, we also pose a natural conjecture for the best upper bound. [ABSTRACT FROM AUTHOR]

We study data structures to answer window queries using stochastic input sequences. The first problem is the most likely maximal point in a query window: Let α 1 , ... , α c be constants, with 0 < α 1 < α 2 < ... < α c < 1. Let P = P 1 ∪ P 2 ∪ ... ∪ P c be a set of n points in ℝ d , for some fixed d. For i = 1 , 2 , ... , c , each point in P i is associated with a probability α i of existence. A point p = (x 1 , ... , x d) in P is on the maximal layer of P if there is no other point q = (x 1 ′ , ... , x d ′) in P such that x 1 ′ > x 1 , x 2 ′ > x 2 , ... ,  and  x d ′ > x d . Consider a random subset of P obtained by including, for i = 1 , 2 , ... , c , each point of P i independently with probability α i . For a query interval [ i , j ] , with i ≤ j , we report the point in P i , j = (p i , ... , p j) that has the highest probability to be on the maximal layer of P i , j in O (1) time using O (n log n) space. We solve a special problem as follows. A sequence P of n points in ℝ d is given (d ≥ 2), where each point P has a probability ∈ (0 , 1 ] of existence associated with it. Given a query interval [ i , j ] and an integer t with i ≤ t ≤ j , we report the probability of p t to be on the maximal layer of P i , j in O (log d n) time using O (n log d n) space. The second problem we consider is the most likely common element problem. Let 𝒰 = { 1 , 2 , ... , n } be the universe. Let S 1 , S 1 , ... , S m be a sequence of random subsets of 𝒰 such that for p = 1 , ... , m and i = 1 , ... , n , element i is added to S p with probability α p i (independently of other choices). Let τ be a fixed real number with 0 < τ ≤ 1. For query indices p , q , i and j , with 1 ≤ p ≤ q ≤ m and 1 ≤ i ≤ j ≤ n , we decide whether there exists an element k with i ≤ k ≤ j such that Pr (k ∈ ∩ r = p q S r) ≥ τ in O (1) time using O (m n) space and report these elements in O (log n + w) time, where w is the size of the output. [ABSTRACT FROM AUTHOR]

We consider quadrangulations of red and blue points in the plane where each face is convex and no edge connects two points of the same color. In particular, we show that the following problem is NP-hard: Given a finite set  S of points with each point either red or blue, does there exist a convex quadrangulation of  S in such a way that the predefined colors give a valid vertex 2-coloring of the quadrangulation? We consider this as a step towards solving the corresponding long-standing open problem on monochromatic point sets. [ABSTRACT FROM AUTHOR]

Given a set of points in the Euclidean plane, the Euclidean δ -minimum spanning tree (δ -MST) problem is the problem of finding a spanning tree with maximum degree no more than δ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean δ -minimum bottleneck spanning tree (δ -MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When δ ≤ 4 , these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested. [ABSTRACT FROM AUTHOR]

We present improved upper bounds on the spanning ratio of constrained 𝜃 -graphs with at least 6 cones and constrained Yao-graphs with 5 or at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into m disjoint cones, each having aperture 𝜃 = 2 π / m , and adds an edge to the closest vertex in each cone. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. Constrained 𝜃 -graphs are similar to constrained Yao-graphs, but use a different method to determine the closest vertex. We present tight bounds on the spanning ratio of a large family of constrained 𝜃 -graphs. We show that constrained 𝜃 -graphs with 4 k + 2 (k ≥ 1 and integer) cones have a tight spanning ratio of 1 + 2 sin (𝜃 / 2) , where 𝜃 is 2 π / (4 k + 2). We also present improved upper bounds on the spanning ratio of the other families of constrained 𝜃 -graphs. These bounds match the current upper bounds in the unconstrained setting. We also show that constrained Yao-graphs with an even number of cones (m ≥ 8) have spanning ratio at most 1 / (1 − 2 sin (𝜃 / 2)) and constrained Yao-graphs with an odd number of cones (m ≥ 5) have spanning ratio at most 1 / (1 − 2 sin (3 𝜃 / 8)). As is the case with constrained 𝜃 -graphs, these bounds match the current upper bounds in the unconstrained setting, which implies that like in the unconstrained setting using more cones can make the spanning ratio worse. [ABSTRACT FROM AUTHOR]

We present a new algorithm for the widely used density-based clustering method dbscan. For a set of n points in ℝ 2 our algorithm computes the dbscan-clustering in O (n log n) time, irrespective of the scale parameter  𝜀 (and assuming the second parameter MinPts is set to a fixed constant, as is the case in practice). Experiments show that the new algorithm is not only fast in theory, but that a slightly simplified version is competitive in practice and much less sensitive to the choice of 𝜀 than the original dbscan algorithm. We also present an O (n log n) randomized algorithm for hdbscan in the plane — hdbscan is a hierarchical version of dbscan introduced recently — and we show how to compute an approximate version of hdbscan in near-linear time in any fixed dimension. [ABSTRACT FROM AUTHOR]

Helly's theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If S is a set of n points in ℝ d , we say that S is (k , G) -clusterable if it can be partitioned into k clusters (subsets) such that each cluster can be contained in a translated copy of a geometric object G. In this paper, as an application of Helly's theorem, by taking a constant size sample from S , we present a testing algorithm for (k , G) -clustering, i.e., to distinguish between the following two cases: when S is (k , G) -clusterable, and when it is 𝜖 -far from being (k , G) -clusterable. A set S is 𝜖 -far (0 < 𝜖 ≤ 1) from being (k , G) -clusterable if at least 𝜖 n points need to be removed from S in order to make it (k , G) -clusterable. We solve this problem when k = 1 , and G is a symmetric convex object. For k > 1 , we solve a weaker version of this problem. Finally, as an application of our testing result, in the case of clustering with outliers, we show that with high probability one can find the approximate clusters by querying only a constant size sample. [ABSTRACT FROM AUTHOR]

Let and be two discrete point sets in of sizes and , respectively, and let be a given input threshold. The largest common point set problem (LCP) seeks the largest subsets and such that and there exists a transformation that makes the bottleneck distance between and at most . We present two algorithms that solve a relaxed version of this problem under translations in and under rigid motions in the plane, and that takes an additional input parameter . Let be the largest subset size achievable for the given . Our algorithm finds subsets and of size and a transformation such that the bottleneck distance between and is at most . For rigid motions in the plane, the running time is . For translations in , the running time is , where for and for . [ABSTRACT FROM AUTHOR]

We consider the problem of reconstructing the combinatorial structure of a set of points in the plane given partial information on the relative position of the points. This partial information consists of the radial ordering, for each of the points, of the other points around it. We show that this information is sufficient to reconstruct the chirotope, or labeled order type, of the point set, provided its convex hull has size at least four. Otherwise, we show that there can be as many as distinct chirotopes that are compatible with the partial information, and this bound is tight. Our proofs yield polynomial-time reconstruction algorithms. These results provide additional theoretical insights on previously studied problems related to robot navigation and visibility-based reconstruction. [ABSTRACT FROM AUTHOR]

Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delaunay triangulations. Selection lemma type results typically show that there exists a point that is contained in many objects that are induced (spanned) by an underlying point set. In the first selection lemma, we consider the set of all the objects induced by a point set . This question has been widely explored for simplices in , with tight bounds in . In our paper, we prove first selection lemma for other classes of geometric objects like boxes and balls in . We also consider the strong variant of this problem where we add the constraint that the piercing point comes from . We prove an exact result on the strong and the weak variant of the first selection lemma for axis-parallel rectangles and disks (for centrally symmetric point sets). We also show non-trivial bounds on the first selection lemma for axis-parallel boxes and balls in . In the second selection lemma, we consider an arbitrary sized subset of the set of all objects induced by . We study this problem for axis-parallel rectangles and show that there exists a point in the plane that is contained in rectangles. This is an improvement over the previous bound by Smorodinsky and Sharir22 when is almost quadratic. [ABSTRACT FROM AUTHOR]

(I) We exhibit a set of 23 points in the plane that has dilation at least , improving the previous best lower bound of for the worst-case dilation of plane spanners. (II) For every , there exists an -element point set such that the degree dilation of equals in the domain of plane geometric spanners. In the same domain, we show that for every , there exists a an -element point set such that the degree dilation of equals The previous best lower bound of holds for any degree. (III) For every , there exists an -element point set such that the stretch factor of the greedy triangulation of is at least . [ABSTRACT FROM AUTHOR]

Associating the regions of a geographic subdivision with the cells of a grid is a basic operation that is used in various types of maps, like spatially ordered treemaps and Origin-Destination maps (OD maps). In these cases the regular shapes of the grid cells allow easy representation of extra information about the regions. The main challenge is to find an association that allows a user to find a region in the grid quickly. We call the representation of a set of regions as a grid a grid map. We introduce a new approach to solve the association problem for grid maps by formulating it as a point set matching problem: Given two sets (the centroids of the regions) and (the grid centres) of points in the plane, compute an optimal one-to-one matching between and . We identify three optimisation criteria that are important for grid map layout: maximise the number of adjacencies in the grid that are also adjacencies of the regions, minimise the sum of the distances between matched points, and maximise the number of pairs of points in for which the matching preserves the directional relation (SW, NW, etc.). We consider matchings that minimise the -distance (Manhattan-distance), the ranked -distance, and the -distance, since one can expect that minimising distances implicitly helps to fulfill the other criteria. We present algorithms to compute such matchings and perform an experimental comparison that also includes a previous method to compute a grid map. The experiments show that our more global, matching-based algorithm outperforms previous, more local approaches with respect to all three optimisation criteria. [ABSTRACT FROM AUTHOR]

In 1979 Conway, Croft, Erdős and Guy proved that every set S of n points in general position in the plane determines at least obtuse angles and also presented a special set of n points to show the upper bound on the minimum number of obtuse angles among all sets S. We prove that every set S of n points in convex position determines at least obtuse angles, hence matching the upper bound (up to sub-cubic terms) in this case. Also on the other side, for point sets with low rectilinear crossing number, the lower bound on the minimum number of obtuse angles is improved. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in ℝd in general position. A set ℋ of k-flats is called an mk-stabber of S if the relative interior of any m-simplex with vertices in S is intersected by at least one element of ℋ. In this paper we give lower and upper bounds on the size of minimum mk-stabbers of point sets in ℝd and in general position. We study mainly mk-stabbers in the plane and in ℝ3. [ABSTRACT FROM AUTHOR]

We present an algorithm that takes as input a finite point set in ℝ m, and performs a perturbation that guarantees that the Delaunay triangulation of the resulting perturbed point set has quantifiable stability with respect to the metric and the point positions. There is also a guarantee on the quality of the simplices: they cannot be too at. The algorithm provides an alternative tool to the weighting or refinement methods to re-move poorly shaped simplices in Delaunay triangulations of arbitrary dimension, but in addition it provides a guarantee of stability for the resulting triangulation. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a natural variation of the problem of computing all bichro-matic intersections between two sets of segments. Given two sets R and B of n points in the plane defining two sets of segments, say red and blue, we present an O(n²) time and space algorithm for solving the problem of reporting the set of segments of each color intersected by segments of the other color. We also prove that this problem is 3-Sum hard and provide some illustrative examples of several point configuration. [ABSTRACT FROM AUTHOR]

Graph-theoretic properties of certain proximity graphs defined on planar point sets are investigated. We first consider some of the most common proximity graphs of the family of the Delaunay graph, and study their number of edges, minimum and maximum degree, clique number, and chromatic number. In the second part of the paper we focus on the higher order versions of some of these graphs and give bounds on the same parameters. [ABSTRACT FROM AUTHOR]

A planar point set S is an (i, t) set of ghost chimneys if there exist lines H0, H1,...,Ht-1 such that the orthogonal projection of S onto Hj consists of exactly i + j distinct points. We give upper and lower bounds on the maximum value of t in an (i, t) set of ghost chimneys, showing that it is linear in i. [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]

Let R and B be sets of red and blue points in the plane in general position. We study the problem of computing a k-level binary space partition (BSP) tree to classify/separate R and B, such that the tree defines a linear decision at each internal node and each leaf of the tree corresponds to a (convex) cell of the partition that contains only red or only blue points. Specifically, we show that a 2-level tree can be computed, if one exists, in time O(n2). We show that a minimum-level (3 ≤ k ≤ n) tree can be computed in time nO( n). In the special case of axis-parallel partitions, we show that 2-level and 3-level trees can be computed in time O(n), while a minimum-level tree can be computed in time O(n5). [ABSTRACT FROM AUTHOR]

Given a set S of n points in the plane, the disjoint two-rectangle covering problem is to find a pair of disjoint rectangles such that their union contains S and the area of the larger rectangle is minimized. In this paper we consider two variants of this optimization problem: (1) the rectangles are allowed to be reoriented freely while restricting them to be parallel to each other, and (2) one rectangle is restricted to be axis-parallel but the other rectangle is allowed to be reoriented freely. For both of the problems, we present O(n2log n)-time algorithms using O(n) space. [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]

No abstract received. [ABSTRACT FROM AUTHOR]