Point Set Topology

Lecture notes about point set toplogy

Resampling Strategies for Deforming MLS Surfaces

Moving-least-squares (MLS) surfaces undergoing large deformations need periodic regeneration of the point set (point-set resampling) so as to keep the point-set density quasi-uniform. Previous work by the authors dealt with algebraic MLS surfaces, and proposed a resampling strategy based on defining the new points at the intersections of the MLS surface with a suitable set of rays. That strategy has very low memory requirements and is easy to parallelize. In this article new resampling strategies with reduced CPU-time cost are explored. The basic idea is to choose as set of rays the lines of a regular, Cartesian grid, and to fully exploit this grid: as data structure for search queries, as spatial structure for traversing the surface in a continuation-like algorithm, and also as approximation grid for an interpolated version of the MLS surface. It is shown that in this way a very simple and compact resampling technique is obtained, which cuts the resampling cost by half with affordable memory requirements.

Graphical models and point set matching

Point pattern matching in Euclidean Spaces is one of the fundamental problems in Pattern Recognition, having applications ranging from Computer Vision to Computational Chemistry. Whenever two complex patterns are encoded by two sets of points identifying their key features, their comparison can be seen as a point pattern matching problem. This work proposes a single approach to both exact and inexact point set matching in Euclidean Spaces of arbitrary dimension. In the case of exact matching, it is assured to find an optimal solution. For inexact matching (when noise is involved), experimental results confirm the validity of the approach. We start by regarding point pattern matching as a weighted graph matching problem. We then formulate the weighted graph matching problem as one of Bayesian inference in a probabilistic graphical model. By exploiting the existence of fundamental constraints in patterns embedded in Euclidean Spaces, we prove that for exact point set matching a simple graphical model is equivalent to the full model. It is possible to show that exact probabilistic inference in this simple model has polynomial time complexity with respect to the number of elements in the patterns to be matched. This gives rise to a technique that for exact matching provably finds a global optimum in polynomial time for any dimensionality of the underlying Euclidean Space. Computational experiments comparing this technique with well-known probabilistic relaxation labeling show significant performance improvement for inexact matching. The proposed approach is significantly more robust under augmentation of the sizes of the involved patterns. In the absence of noise, the results are always perfect.

Kernel density correlation based non-rigid point set matching for statistical model-based 2D/3D reconstruction

This paper presents a kernel density correlation based nonrigid point set matching method and shows its application in statistical model based 2D/3D reconstruction of a scaled, patient-specific model from an un-calibrated x-ray radiograph. In this method, both the reference point set and the floating point set are first represented using kernel density estimates. A correlation measure between these two kernel density estimates is then optimized to find a displacement field such that the floating point set is moved to the reference point set. Regularizations based on the overall deformation energy and the motion smoothness energy are used to constraint the displacement field for a robust point set matching. Incorporating this non-rigid point set matching method into a statistical model based 2D/3D reconstruction framework, we can reconstruct a scaled, patient-specific model from noisy edge points that are extracted directly from the x-ray radiograph by an edge detector. Our experiment conducted on datasets of two patients and six cadavers demonstrates a mean reconstruction error of 1.9 mm

On the Erdos-Szekeres n-interior point problem

The n-interior point variant of the Erdos-Szekeres problem is to show the following: For any n, n-1, every point set in the plane with sufficient number of interior points contains a convex polygon containing exactly n-interior points. This has been proved only for n-3. In this paper, we prove it for pointsets having atmost logarithmic number of convex layers. We also show that any pointset containing atleast n interior points, there exists a 2-convex polygon that contains exactly n-interior points.

On the Erdos-Szekeres n-interior-point problem

The n-interior-point variant of the Erdos Szekeres problem is the following: for every n, n >= 1, does there exist a g(n) such that every point set in the plane with at least g(n) interior points has a convex polygon containing exactly n interior points. The existence of g(n) has been proved only for n <= 3. In this paper, we show that for any fixed r >= 2, and for every n >= 5, every point set having sufficiently large number of interior points and at most r convex layers contains a subset with exactly n interior points. We also consider a relaxation of the notion of convex polygons and show that for every n, n >= 1, any point set with at least n interior points has an almost convex polygon (a simple polygon with at most one concave vertex) that contains exactly n interior points. (C) 2013 Elsevier Ltd. All rights reserved.

Fixed-orientation equilateral triangle matching of point sets

Given a point set P and a class C of geometric objects, G(C)(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C is an element of C containing both p and q but no other points from P. We study G(del)(P) graphs where del is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Theta(6) graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G(del)(P) always contains a matching of size at least vertical bar P vertical bar-1/3] and this bound is tight. We also give some structural properties of G(star)(P) graphs, where is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G(star)(P) is simply a path. Through the equivalence of G(star)(P) graphs with Theta(6) graphs, we also derive that any Theta(6) graph can have at most 5n-11 edges, for point sets in general position. (C) 2013 Elsevier B.V. All rights reserved.

Involutions whose fixed set has three or four components: a small codimension phenomenon

Let T : M → M be a smooth involution on a closed smooth manifold and F = n j=0 F j the fixed point set of T, where F j denotes the union of those components of F having dimension j and thus n is the dimension of the component of F of largest dimension. In this paper we prove the following result, which characterizes a small codimension phenomenon: suppose that n ≥ 4 is even and F has one of the following forms: 1) F = F n ∪ F 3 ∪ F 2 ∪ {point}; 2) F = F n ∪ F 3 ∪ F 2 ; 3) F = F n ∪ F 3 ∪ {point}; or 4) F = F n ∪ F 3 . Also, suppose that the normal bundles of F n, F 3 and F 2 in M do not bound. If k denote the codimension of F n, then k ≤ 4. Further, we construct involutions showing that this bound is best possible in the cases 2) and 4), and in the cases 1) and 3) when n is of the form n = 4t, with t ≥ 1.

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.

Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637(k) n(O(1)).

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

Results on proximal and generalized weak proximal contractions including the case of iteration-dependent range sets

This paper presents some further results on proximal and asymptotic proximal contractions and on a class of generalized weak proximal contractions in metric spaces. The generalizations are stated for non-self-mappings of the forms for and , or , subject to and , such that converges uniformly to T, and the distances are iteration-dependent, where , , and are non-empty subsets of X, for , where is a metric space, provided that the set-theoretic limit of the sequences of closed sets and exist as and that the countable infinite unions of the closed sets are closed. The convergence of the sequences in the domain and the image sets of the non-self-mapping, as well as the existence and uniqueness of the best proximity points, are also investigated if the metric space is complete. Two application examples are also given, being concerned, respectively, with the solutions through pseudo-inverses of both compatible and incompatible linear algebraic systems and with the parametrical

基于Stewart平台六维力传感器的分区静态标定方法

基于Stewart平台的六维力传感器具有结构紧凑、刚度大、量程宽等特点,它在工业机器人、空间站对接等领域具有广泛的应用前景。好的标定方法是正确使用传感器的基础。由于基于Stewart平台的六维力传感器是一个复杂的非线性系统,所以采用常规的线性标定方法必将带来较大的标定误差从而影响其使用性能。标定的实质是,由测量值空间到理论值空间的映射函数的确定过程。由函数逼近理论可知,当只在已知点集上给出函数值时,可用多项式或分段多项式等较简单函数逼近待定函数。基于上述思想,本文将整个测量空间划分为若干连续的子测量空间,再对每个子空间进行线性标定,从而提高了整个测量系统的标定精度。实验分析结果表明了该标定方法有效。

基于点集曲面投影算法的自由曲面匹配

测量数据的精确定位是实现复杂曲面加工检测的关键,针对测量点云数据与NURBS表示的CAD自由曲面模型匹配中求最近点计算方面存在的问题,提出了一种简单、有效的寻找最近点的方法。该方法与由测量点集评估给定曲面上的最近点的传统算法相反,采用点集曲面(point set surface,PSS)投影算法,对给定自由曲面模型上有限个点与不附加任何几何和拓扑信息的散乱点集之间进行粗匹配获得初始位置,进而以最近点迭代算法(ICP)完成测量数据定位的精确调整,达到全局及局部最优的目标。实验结果表明,采用PSS投影算法法寻找最近点不仅效率高,而且能得到全局匹配结果,可以为精匹配提供较好的计算初值,减少了ICP算法进行二次匹配时,迭代次数及执行时间并且精度得到了较大提高。