Planar point sets with large minimum convex decompositions

We show the existence of sets with n points (n ? 4) for which every convex decomposition contains more than (35/32)n?(3/2) polygons,which refutes the conjecture that for every set of n points there is a convex decomposition with at most n+C polygons. For sets having exactly three extreme pointswe show that more than n+sqr(2(n ? 3))?4 polygons may be necessary to form a convex decomposition.

Point Set Topology

Lecture notes about point set toplogy

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

Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints

* A preliminary version of this paper was presented at XI Encuentros de Geometr´ia Computacional, Santander, Spain, June 2005.

Assembly accuracy analysis for small components with a planar surface in large-scale metrology

Large-scale mechanical products, such as aircraft and rockets, consist of large numbers of small components, which introduce additional difficulty for assembly accuracy and error estimation. Planar surfaces as key product characteristics are usually utilised for positioning small components in the assembly process. This paper focuses on assembly accuracy analysis of small components with planar surfaces in large-scale volume products. To evaluate the accuracy of the assembly system, an error propagation model for measurement error and fixture error is proposed, based on the assumption that all errors are normally distributed. In this model, the general coordinate vector is adopted to represent the position of the components. The error transmission functions are simplified into a linear model, and the coordinates of the reference points are composed by theoretical value and random error. The installation of a Head-Up Display is taken as an example to analyse the assembly error of small components based on the propagation model. The result shows that the final coordination accuracy is mainly determined by measurement error of the planar surface in small components. To reduce the uncertainty of the plane measurement, an evaluation index of measurement strategy is presented. This index reflects the distribution of the sampling point set and can be calculated by an inertia moment matrix. Finally, a practical application is introduced for validating the evaluation index.

Splat-based surface reconstruction from defect-laden point sets

We introduce a method for surface reconstruction from point sets that is able to cope with noise and outliers. First, a splat-based representation is computed from the point set. A robust local 3D RANSAC-based procedure is used to filter the point set for outliers, then a local jet surface - a low-degree surface approximation - is fitted to the inliers. Second, we extract the reconstructed surface in the form of a surface triangle mesh through Delaunay refinement. The Delaunay refinement meshing approach requires computing intersections between line segment queries and the surface to be meshed. In the present case, intersection queries are solved from the set of splats through a 1D RANSAC procedure

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.

Comparison between the 1% and 2% ibopamine provocative test in primary open-angle glaucoma patients: sensitivity, specificity and tolerability

PURPOSE: To compare intraocular pressure (IOP) rise in normal individuals and primary open-angle glaucoma patients and the safety and efficacy of ibopamine eye drops in different concentrations as a provocative test for glaucoma. METHODS: Glaucoma patients underwent (same eye) the ibopamine provocative test with two concentrations, 1% and 2%, in a random sequence at least 3 weeks apart, but not more than 3 months. The normal individuals were randomly submitted to one of the concentrations of ibopamine (1% and 2%). The test was considered positive if there was an IOP rise greater than 3 or 4 mmHg at 30 or 45 minutes to test which subset of the test has the best sensitivity (Se)/specificity (Sp). RESULTS: There was no statistically significant difference in any of the IOP measurements, comparing 1% with 2% ibopamine. The IOP was significantly higher at 30 and 45 minutes with both concentrations (p<0.001). The best sensitivity/specificity ratio was achieved with the cutoff point set as greater than 3 mmHg at 45 minutes with 2% ibopamine (area under the ROC curve: 0.864, Se: 84.6%; Sp:73.3%). All patients described a slight burning after ibopamine's instillation. CONCLUSION: 2% ibopamine is recommended as a provocative test for glaucoma. Because both concentrations have similar ability to rise IOP, 1% ibopamine may be used to treat ocular hypotony.

Parts, places, and perspectives : a theory of spatial relations based an mereotopology and convexity

This thesis suggests to carry on the philosophical work begun in Casati's and Varzi's seminal book Parts and Places, by extending their general reflections on the basic formal structure of spatial representation beyond mereotopology and absolute location to the question of perspectives and perspective-dependent spatial relations. We show how, on the basis of a conceptual analysis of such notions as perspective and direction, a mereotopological theory with convexity can express perspectival spatial relations in a strictly qualitative framework. We start by introducing a particular mereotopological theory, AKGEMT, and argue that it constitutes an adequate core for a theory of spatial relations. Two features of AKGEMT are of particular importance: AKGEMT is an extensional mereotopology, implying that sameness of proper parts is a sufficient and necessary condition for identity, and it allows for (lower- dimensional) boundary elements in its domain of quantification. We then discuss an extension of AKGEMT, AKGEMTS, which results from the addition of a binary segment operator whose interpretation is that of a straight line segment between mereotopological points. Based on existing axiom systems in standard point-set topology, we propose an axiomatic characterisation of the segment operator and show that it is strong enough to sustain complex properties of a convexity predicate and a convex hull operator. We compare our segment-based characterisation of the convex hull to Cohn et al.'s axioms for the convex hull operator, arguing that our notion of convexity is significantly stronger. The discussion of AKGEMTS defines the background theory of spatial representation on which the developments in the second part of this thesis are built. The second part deals with perspectival spatial relations in two-dimensional space, i.e., such relations as those expressed by 'in front of, 'behind', 'to the left/right of, etc., and develops a qualitative formalism for perspectival relations within the framework of AKGEMTS. Two main claims are defended in part 2: That perspectival relations in two-dimensional space are four- place relations of the kind R(x, y, z, w), to be read as x is i?-related to y as z looks at w; and that these four-place structures can be satisfactorily expressed within the qualitative theory AKGEMTS. To defend these two claims, we start by arguing for a unified account of perspectival relations, thus rejecting the traditional distinction between 'relative' and 'intrinsic' perspectival relations. We present a formal theory of perspectival relations in the framework of AKGEMTS, deploying the idea that perspectival relations in two-dimensional space are four-place relations, having a locational and a perspectival part and show how this four-place structure leads to a unified framework of perspectival relations. Finally, we present a philosophical motivation to the idea that perspectival relations are four-place, cashing out the thesis that perspectives are vectorial properties and argue that vectorial properties are relations between spatial entities. Using Fine's notion of "qua objects" for an analysis of points of view, we show at last how our four-place approach to perspectival relations compares to more traditional understandings.

Génération et édition de textures géométriques représentées par des ensembles de points

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Rendimiento operativo de la tamizacion doble ajustada por raza para la deteccion de aneuploidias en poblacion colombiana

Actualmente, los algoritmos utilizados para la detección de alteraciones cromosómicas se han basado en los resultados obtenidos de poblaciones caucásicas, afrocaribeñas y asiáticas, las cuales, no tienen las mismas características de la raza mestiza. De allí, surgió el interés de realizar un estudio que permitiera determinar los valores de los marcadores serológicos, empleados en la tamización de aneuploidías, en población latina, para establecer un punto de corte ajustado a la raza mestiza. Se encuentra en desarrollo un estudio de validación de prueba diagnóstica, cuyos avances se presentan a continuación. En esta investigación, hasta el momento, se han incluido 1418 pacientes entre 11-13.6 semanas, sometidas a tamización combinada para la detección de aneuploidías. Se realizó un ajuste por raza de valores de medianas y sus múltiplos para los marcadores y se determinó el rendimiento operativo de la prueba luego de dicho ajuste. Posteriormente, se realizó una comparación entre ambas pruebas. Los niveles de B-hCG son 17.1 % más bajos en población mestiza colombiana, comparado con población caucásica y los niveles de PAPP-A son 19% inferiores. Las tasas de detección de la prueba, utilizando los valores convencionales, son del 60 % y, luego del ajuste por raza, es del 53 %. Haciendo el cálculo de riesgo, utilizando los nuevos múltiplos de mediana, no existen diferencias en aplicar la tamización con los valores convencionales entre las semanas 11 y 12 pero, en semana 13, los valores aplicados a población caucásica presentan una mejor tasa de detección que utilizar la prueba ajustada.

Lecture notes

Lecture notes in LaTex

Lecture notes pdf

Lecture notes in PDF

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.