Approximate input sensitive algorithms for point pattern matching

We study input sensitive algorithms for point pattern matching under various transformations and the Hausdorff metric as a distance function. Given point sets P and Q in the plane, the problem of point pattern matching is to determine whether P is similar to some portion of Q, where P may undergo transformations from a group G of allowed transformations. All algorithms are based on methods for extracting small subsets from Q that can be matched to a small subset of P. The runtime is proportional to the number k of these subsets. Let d be the number of points in P that are needed to define a transformation in G. The key observation is that for some set B⊂P of cardinality larger than d, the number of subsets of Q of this cardinality that match B, is practically small, as the problem becomes more constrained. We present methods to extract efficiently all these subsets in Q. We provide algorithms for homothetic, rigid and similarity transformations in the plane and give a general method that works for any dimension and for any group of transformations. The runtime of our algorithms depends roughly linearly on the number of subsets k, in addition to an factor. Thus our approximate matching algorithms run roughly in time , where m and n are the number of points in P and Q, respectively. The constants hidden in the big O vary depending on the group of transformations G.     

Applying graphics hardware to achieve extremely fast geometric pattern matching in two and three dimensional transformation space

We present a GPU-based approach to geometric pattern matching. We reduce this problem to finding the depth (maximally covered point) of an arrangement of polytopes in transformation space and describe hardware assisted (GPU) algorithms which exploit the available set of graphics operations to perform a fast rasterized depth computation. We give two alternatives, one is for translation + scale and the other is for rigid transformations, both have 3-parameters transformation space. We give extensive experimental results showing the running time of our method and its dependence on various parameters.     

Simple algorithms for partial point set pattern matching under rigid motion

This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (n?k), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined ε-neighborhood region around some point in P. The proposed algorithm for the exact matching needs O(n²) space and preprocessing time. The existence of a match for a given query set Q can be checked in time in the worst-case, where α is the maximum number of equidistant pairs of point in P. For a set of n points, α may be O(n^4/3) in the worst-case. Some applications of the partial point set pattern matching are then illustrated. Experimental results on random point sets and some fingerprint databases show that, in practice, the computation time is much smaller than the worst-case requirement. The algorithm is then extended for checking the exact match of a set of k line segments in the query set with a k-subset of n line segments in the sample set under rigid motion in time. Next, a simple version of the approximate matching problem is studied where one point of Q exactly matches with a point of P, and each of the other points of Q lie in the ε-neighborhood of some point of P. The worst-case time and space complexities of the proposed algorithm are and O(n), respectively. The proposed algorithms will find many applications to fingerprint matching, image registration, and object recognition.     

A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation

To determine the similarity of two point sets is one of the major goals of pattern recognition and computer graphics. One widely studied similarity measure for point sets is the Hausdorff distance. So far, various computational methods have been proposed for computing the minimum Hausdorff distance. In this paper, we propose a new algorithm to compute the minimum Hausdorff distance between two point sets on a line under translation, which outperforms other existing algorithms in terms of efficiency despite its complexity of O((m+n)lg(m+n)), where m and n are the sizes of two point sets.     

Improved Approximation Bounds for Planar Point Pattern Matching

We analyze the performance of simple algorithms for matching two planar point sets under rigid transformations so as to minimize the directed Hausdorff distance between the sets. This is a well studied problem in computational geometry. Goodrich, Mitchell, and Orletsky presented a very simple approximation algorithm for this problem, which computes transformations based on aligning pairs of points. They showed that their algorithm achieves an approximation ratio of 4. We introduce a modification to their algorithm, which is based on aligning midpoints rather than endpoints. This modification has the same simplicity and running time as theirs, and we show that it achieves a better approximation ratio of roughly 3.14. We also analyze the approximation ratio in terms of a instance-specific parameter that is based on the ratio between diameter of the pattern set to the optimum Hausdorff distance. We show that as this ratio increases (as is common in practical applications) the approximation ratio approaches 3 in the limit. We also investigate the performance of the algorithm by Goodrich et al. as a function of this ratio, and present nearly matching lower bounds on the approximation ratios of both algorithms. This work was supported by the National Science Foundation under grants CCR-0098151 and CCF-0635099.     

On the parameterized complexity of d-dimensional point set pattern matching

Deciding whether two n-point sets A,B∈Rd are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT.When |A|=m<|B|=n, the problem becomes that of deciding whether A is congruent to a subset of B and is known to be NP-complete. We show that point subset congruence, with d as a parameter, is W[1]-hard, and that it cannot be solved in O(mno(d))-time, unless SNP⊂DTIME(²o(n)). This shows that, unless FPT=W[1], the problem of finding an isometry of A that minimizes its directed Hausdorff distance, or its Earth Mover's Distance, to B, is not in FPT.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^{1.5k –1.5k} ((n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, is the inverse Ackermann function, and 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ) times the weight of a minimum weight complete matching.This research was supported by a fellowship from the Shell Foundation.     

Inexact Bayesian point pattern matching for linear transformations

We introduce a novel Bayesian inexact point pattern matching model that assumes that a linear transformation relates the two sets of points. The matching problem is inexact due to the lack of one-to-one correspondence between the point sets and the presence of noise. The algorithm is itself inexact; we use variational Bayesian approximation to estimate the posterior distributions in the face of a problematic evidence term. The method turns out to be similar in structure to the iterative closest point algorithm.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

On plane spanning trees and cycles of multicolored point sets with few intersections

Let P₁,…,Pk be a collection of disjoint point sets in R² in general position. We prove that for each 1?i?k we can find a plane spanning tree Ti of Pi such that the edges of T₁,…,Tk intersect at most , where n is the number of points in P₁∪?∪Pk. If the intersection of the convex hulls of P₁,…,Pk is nonempty, we can find k spanning cycles such that their edges intersect at most (k−1)n times, this bound is tight. We also prove that if P and Q are disjoint point sets in general position, then the minimum weight spanning trees of P and Q intersect at most 8n times, where |P∪Q|=n (the weight of an edge is its length).     

Hitting sets when the VC-dimension is small

We present an approximation algorithm for the hitting set problem when the VC-dimension of the set system is small. Our algorithm uses a linear programming relaxation to compute a probability measure for which ?-nets are always hitting sets (see Corollary 15.6 in Pach and Agarwal [Combinatorial Geometry, J. Wiley, New York, 1995]). The comparable algorithm of Brönnimann and Goodrich [Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995) 463] computes such a probability measure by an iterative reweighting technique. The running time of our algorithm is comparable with theirs, and the approximation ratio is smaller by a constant factor. We also show how our algorithm can be parallelized and extended to the minimum cost hitting set problem.     

The directed Hausdorff distance between imprecise point sets

We consider the directed Hausdorff distance between point sets in the plane, where one or both point sets consist of imprecise points. An imprecise point is modelled by a disc given by its centre and a radius. The actual position of an imprecise point may be anywhere within its disc. Due to the direction of the Hausdorff distance and whether its tight upper or lower bound is computed, there are several cases to consider. For every case we either show that the computation is NP-hard or we present an algorithm with a polynomial running time. Further we give several approximation algorithms for the hard cases and show that one of them cannot be approximated better than with factor 3, unless P=NP.     

An algorithm for projective point matching in the presence of spurious points

Point matching is the task of finding correspondences between two sets of points such that the two sets of points are aligned with each other. Pure point matching uses only the location of the points to constrain the problem. This is a problem with broad practical applications, but it has only been well studied when the geometric transformation relating the two point sets is of a relatively low order. Here we present a heuristic local search algorithm that can find correspondences between point sets in two dimensions that are related by a projective transform. Point matching is a harder problem when spurious points appear in the sets to be matched. We present a heuristic algorithm which minimizes the effects of spurious points.     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

A fast heuristic based on spacefilling curves for minimum-weight matching in the plane

We present a heuristic to find a good matching on n points in the plane. It is essentially sorting and so runs in O(n log n) worst-case time and linear expected time. Its performance is competitive with that of previously suggested methods. However, it has the advantages of being trivial to code and of being indifferent to the choice of metric or the probability distribution from which the points are drawn.     

Spectral correspondence for point pattern matching

This paper investigates the correspondence matching of point-sets using spectral graph analysis. In particular, we are interested in the problem of how the modal analysis of point-sets can be rendered robust to contamination and drop-out. We make three contributions. First, we show how the modal structure of point-sets can be embedded within the framework of the EM algorithm. Second, we present several methods for computing the probabilities of point correspondences from the modes of the point proximity matrix. Third, we consider alternatives to the Gaussian proximity matrix. We evaluate the new method on both synthetic and real-world data. Here we show that the method can be used to compute useful correspondences even when the level of point contamination is as large as 50%. We also provide some examples on deformed point-set tracking.     

A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane

Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham’s scan, Andrew’s monotone chain, Jarvis’ gift wrapping, Chan’s, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space.     

Lower bounds for testing Euclidean Minimum Spanning Trees

The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G=(P,E) on a set of points in the two-dimensional plane is a minimum spanning tree with respect to the Euclidean distance. Czumaj et al. [A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] gave a 1-sided-error non-adaptive property-tester for this task of query complexity . We show that every non-adaptive (not necessarily 1-sided-error) property-tester for this task has a query complexity of , implying that the test in [A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] is of asymptotically optimal complexity. We further prove that every adaptive property-tester has query complexity of Ω(n1/3). Those lower bounds hold even when the input graph is promised to be a bounded degree tree.