Convergence analysis and validation of low cost distance metrics for computational cost reduction of the Iterative Closest Point algorithm

The Iterative Closest Point algorithm (ICP) is commonly used in engineering applications to solve the rigid registration problem of partially overlapped point sets which are pre-aligned with a coarse estimate of their relative positions. This iterative algorithm is applied in many areas such as the medicine for volumetric reconstruction of tomography data, in robotics to reconstruct surfaces or scenes using range sensor information, in industrial systems for quality control of manufactured objects or even in biology to study the structure and folding of proteins. One of the algorithm’s main problems is its high computational complexity (quadratic in the number of points with the non-optimized original variant) in a context where high density point sets, acquired by high resolution scanners, are processed. Many variants have been proposed in the literature whose goal is the performance improvement either by reducing the number of points or the required iterations or even enhancing the complexity of the most expensive phase: the closest neighbor search. In spite of decreasing its complexity, some of the variants tend to have a negative impact on the final registration precision or the convergence domain thus limiting the possible application scenarios. The goal of this work is the improvement of the algorithm’s computational cost so that a wider range of computationally demanding problems from among the ones described before can be addressed. For that purpose, an experimental and mathematical convergence analysis and validation of point-to-point distance metrics has been performed taking into account those distances with lower computational cost than the Euclidean one, which is used as the de facto standard for the algorithm’s implementations in the literature. In that analysis, the functioning of the algorithm in diverse topological spaces, characterized by different metrics, has been studied to check the convergence, efficacy and cost of the method in order to determine the one which offers the best results. Given that the distance calculation represents a significant part of the whole set of computations performed by the algorithm, it is expected that any reduction of that operation affects significantly and positively the overall performance of the method. As a result, a performance improvement has been achieved by the application of those reduced cost metrics whose quality in terms of convergence and error has been analyzed and validated experimentally as comparable with respect to the Euclidean distance using a heterogeneous set of objects, scenarios and initial situations.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Characterizing and recognizing weak visibility polygons

A polygon is said to be a weak visibility polygon if every point of the polygon is visible from some point of an internal segment. In this paper we derive properties of shortest paths in weak visibility polygons and present a characterization of weak visibility polygons in terms of shortest paths between vertices. These properties lead to the following efficient algorithms: (i) an O(E) time algorithm for determining whether a simple polygon P is a weak visibility polygon and for computing a visibility chord if it exist, where E is the size of the visibility graph of P and (ii) an O(n2) time algorithm for computing the maximum hidden vertex set in an n-sided polygon weakly visible from a convex edge.

From the Icosahedron to Natural Triangulations of CP(2) and S(2) x S(2)

We present two constructions in this paper: (a) a 10-vertex triangulation CP(10)(2) of the complex projective plane CP(2) as a subcomplex of the join of the standard sphere (S(4)(2)) and the standard real projective plane (RP(6)(2), the decahedron), its automorphism group is A(4); (b) a 12-vertex triangulation (S(2) x S(2))(12) of S(2) x S(2) with automorphism group 2S(5), the Schur double cover of the symmetric group S(5). It is obtained by generalized bistellar moves from a simplicial subdivision of the standard cell structure of S(2) x S(2). Both constructions have surprising and intimate relationships with the icosahedron. It is well known that CP(2) has S(2) x S(2) as a two-fold branched cover; we construct the triangulation CP(10)(2) of CP(2) by presenting a simplicial realization of this covering map S(2) x S(2) -> CP(2). The domain of this simplicial map is a simplicial subdivision of the standard cell structure of S(2) x S(2), different from the triangulation alluded to in (b). This gives a new proof that Kuhnel's CP(9)(2) triangulates CP(2). It is also shown that CP(10)(2) and (S(2) x S(2))(12) induce the standard piecewise linear structure on CP(2) and S(2) x S(2) respectively.

Conflict-Free Coloring for Rectangle Ranges Using O(n.382) Colors

Given a set of points P ⊆ R2, a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each nonempty axisparallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T . This notion has been the subject of recent interest and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to base stations (points) such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R2 can be conflict-free colored with O(nβ∗+o(1)) colors in expected polynomial time, where β∗ = 3−√5 2 < 0.382.

A Triangulation of CP3 as Symmetric Cube of S-2

The symmetric group acts on the Cartesian product (S (2)) (d) by coordinate permutation, and the quotient space is homeomorphic to the complex projective space a'',P (d) . We used the case d=2 of this fact to construct a 10-vertex triangulation of a'',P (2) earlier. In this paper, we have constructed a 124-vertex simplicial subdivision of the 64-vertex standard cellulation of (S (2))(3), such that the -action on this cellulation naturally extends to an action on . Further, the -action on is ``good'', so that the quotient simplicial complex is a 30-vertex triangulation of a'',P (3). In other words, we have constructed a simplicial realization of the branched covering (S (2))(3)-> a'',P (3).

Efficient external memory structures for range-aggregate queries

We present external memory data structures for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points in R-d, compute the aggregate of the weights of the points that lie inside a d-dimensional orthogonal query rectangle. The aggregates we consider in this paper include COUNT, sum, and MAX. First, we develop a structure for answering two-dimensional range-COUNT queries that uses O(N/B) disk blocks and answers a query in O(log(B) N) I/Os, where N is the number of input points and B is the disk block size. The structure can be extended to obtain a near-linear-size structure for answering range-sum queries using O(log(B) N) I/Os, and a linear-size structure for answering range-MAX queries in O(log(B)(2) N) I/Os. Our structures can be made dynamic and extended to higher dimensions. (C) 2012 Elsevier B.V. All rights reserved.

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.

On piercing (pseudo)lines and boxes

We say a family of geometric objects C has (l;k)-property if every subfamily C0C of cardinality at most lisk- piercable. In this paper we investigate the existence of g(k;d)such that if any family of objects C in Rd has the (g(k;d);k)-property, then C is k-piercable. Danzer and Gr̈ unbaum showed that g(k;d)is infinite for fami-lies of boxes and translates of centrally symmetric convex hexagons. In this paper we show that any family of pseudo-lines(lines) with (k2+k+ 1;k)-property is k-piercable and extend this result to certain families of objects with discrete intersections. This is the first positive result for arbitrary k for a general family of objects. We also pose a relaxed ver-sion of the above question and show that any family of boxes in Rd with (k2d;k)-property is 2dk- piercable.

Hardness results for computing optimal locally Gabriel graphs

Delaunay and Gabriel graphs are widely studied geo-metric proximity structures. Motivated by applications in wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Lo-cally Gabriel Graphs (LGGs) have been proposed. We propose another generalization of LGGs called Gener-alized Locally Gabriel Graphs (GLGGs) in the context when certain edges are forbidden in the graph. Unlike a Gabriel Graph, there is no unique LGG or GLGG for a given point set because no edge is necessarily in-cluded or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. We show that computing an edge max-imum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with dilation ≤k is NP-hard. Finally, we give an algorithm to verify whether a given geometric graph G= (V, E) is a valid LGG.

Small strong epsilon nets

Let P be a set of n points in R-d. A point x is said to be a centerpoint of P if x is contained in every convex object that contains more than dn/d+1 points of P. We call a point x a strong centerpoint for a family of objects C if x is an element of P is contained in every object C is an element of C that contains more than a constant fraction of points of P. A strong centerpoint does not exist even for halfspaces in R-2. We prove that a strong centerpoint exists for axis-parallel boxes in Rd and give exact bounds. We then extend this to small strong epsilon-nets in the plane. Let epsilon(S)(i) represent the smallest real number in 0, 1] such that there exists an epsilon(S)(i)-net of size i with respect to S. We prove upper and lower bounds for epsilon(S)(i) where S is the family of axis-parallel rectangles, halfspaces and disks. (C) 2014 Elsevier B.V. All rights reserved.