Segmenting point-sampled surfaces

Extracting features from point-based representations of geometric surface models is becoming increasingly important for purposes such as model classification, matching, and exploration. In an earlier paper, we proposed a multiphase segmentation process to identify elongated features in point-sampled surface models without the explicit construction of a mesh or other surface representation. The preliminary results demonstrated the strength and potential of the segmentation process, but the resulting segmentations were still of low quality, and the segmentation process could be slow. In this paper, we describe several algorithmic improvements to overcome the shortcomings of the segmentation process. To demonstrate the improved quality of the segmentation and the superior time efficiency of the new segmentation process, we present segmentation results obtained for various point-sampled surface models. We also discuss an application of our segmentation process to extract ridge-separated features in point-sampled surfaces of CAD models.

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.

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 .

Free convection heat transfer from vertical cylinders part I: Power law surface temperature variation

This paper reports on the investigations of laminar free convection heat transfer from vertical cylinders and wires whose surface temperature varies along the height according to the relation TW - T∞ = Nxn. The set of boundary layer partial differential equations and the boundary conditions are transformed to a more amenable form and solved by the process of successive substitution. Numerical solutions of the first approximated equations (two-point nonlinear boundary value type of ordinary differential equations) bring about the major contribution to the problem (about 95%), as seen from the solutions of higher approximations. The results reduce to those for the isothermal case when n=0. Criteria for classifying the cylinders into three broad categories, viz., short cylinders, long cylinders and wires, have been developed. For all values of n the same criteria hold. Heat transfer correlations obtained for short cylinders (which coincide with those of flat plates) are checked with those available in the literature. Heat transfer and fluid flow correlations are developed for all the regimes.

Semi-similar solutions of the unsteady compressible second-order boundary layer flow at the stagnation point

Semi-similar solutions of the unsteady compressible laminar boundary layer flow over two-dimensional and axisymmetric bodies at the stagnation point with mass transfer are studied for all the second-order boundary layer effects when the free stream velocity varies arbitrarily with time. The set of partial differential equations governing the unsteady compressible second-order boundary layers representing all the effects are derived for the first time. These partial differential equations are solved numerically using an implicit finite-difference scheme. The results are obtained for two particular unsteady free stream velocity distributions: (a) an accelerating stream and (b) a fluctuating stream. It is observed that the total skin friction and heat transfer are strongly affected by the surface mass transfer and wall temperature. However, their variation with time is significant only for large times. The second-order boundary layer effects are found to be more pronounced in the case of no mass transfer or injection as compared to that for suction. Résumé Des solutions semi-similaires d'écoulement variable compressible de couche limite sur des corps bi-dimensionnels thermique, sont étudiées pour tous les effets de couche limite du second ordre, lorsque la vitesse de l'écoulement libre varie arbitrairement avec le temps. Le systéme d'équations aux dérivées partielles représentant tous les effets est écrit pour la premiére fois. On le résout numériquement á l'aide d'un schéma implicite aux différences finies. Les résultats sont obtenus pour deux cas de vitesse variable d'écoulement libre: (a) un écoulement accéléré et (b) un écoulement fluctuant. On observe que le frottement pariétal total et le transfert de chaleur sont fortement affectés par le transfert de masse et la température pariétaux. Néanmoins, leur variation avec le temps est sensible seulement pour des grandes durées. Les effets sont trouvés plus prononcés dans le cas de l'absence du transfert de masse ou de l'injection par rapport au cas de l'aspiration.

Surface damage of yttria-tetragonal zirconia polycrystals and magnesia-partially-stabilized zirconia in single-point abrasion

Commercially available 3Y-TZP and Mg-PSZ flats mere abraded by a 150 degrees diamond cone at -196 degrees, 25 degrees, 200 degrees, and 400 degrees C. The coefficient of friction, the track width, and the morphological features of the track were recorded. Raman spectroscopy mas used to record the tetragonal-to-monoclinic phase transformation (t --> m) as a function of distance away from the track. The study was undertaken to establish the influence of tangential traction on phase transformation and surface damage.

Effect of surface on the conductance characteristics of Au‐Bi2Sr2CaCu2O8+δ (single crystal) point contact junctions

We report the effect of surface treatments on the dynamic conductance curves (G=dI/dV‐V) of Au‐Bi2Sr2CaCu2O8+δ (single crystal) point contact junctions of variable junction conductances (100 mS≳G≳100 μS). We find that if the crystal surface is cleaved freshly just prior to making contacts, all irreproducible sharp multiple features often observed in tunneling data of Bi(2212) oxide superconductors disappear. If the cleaved crystal surfaces are left under ambient conditions for a few days and the tunneling experiments are repeated, these multiple features reappear. We also find that if the current in the junction is made to pass predominantly through the bulk (and not along the surface), gap features are sharper. The observed conductance curves are fitted to a modified model [G. E. Blonder et al., Phys. Rev. B 25, 4515 (1982)] and estimated gap values are Δ≂28 to 30 meV corresponding to the ratio 2Δ/kBTc ≂ 7.5 with lifetime broadening Γ/Δ≂0.2. We conclude that the sharp multiple features observed in Bi(2212) tunneling curves has no intrinsic origin in the bulk and they arise from the surface only.

Extracting Three Dimensional Surface Model of Human Kidney from the Visible Human Data Set using Free Software

Three dimensional digital model of a representative human kidney is needed for a surgical simulator that is capable of simulating a laparoscopic surgery involving kidney. Buying a three dimensional computer model of a representative human kidney, or reconstructing a human kidney from an image sequence using commercial software, both involve (sometimes significant amount of) money. In this paper, author has shown that one can obtain a three dimensional surface model of human kidney by making use of images from the Visible Human Data Set and a few free software packages (ImageJ, ITK-SNAP, and MeshLab in particular). Images from the Visible Human Data Set, and the software packages used here, both do not cost anything. Hence, the practice of extracting the geometry of a representative human kidney for free, as illustrated in the present work, could be a free alternative to the use of expensive commercial software or to the purchase of a digital model.

Surface chemical studies of Thiobacillus ferrooxidans with reference to copper tolerance

A strain of Thiobacillus ferrooxidans was adapted to grow at higher concentrations of copper by single step culturing in the presence of 20 g/L (0.314 mol/L) cupric ions added to 9K medium. Exposure to copper results in change in the surface chemistry of the microorganism. The isoelectric point of the adapted strain (pI=4.7) was observed to be at a higher pH than that of the wild unadapted strain(pI=2.0). Compared to the wild strain, the copper adapted strain was found to be more hydrophobic and showed enhanced attachment efficiency to the pyrite mineral. The copper adsorption ability of the adapted strain was also found to be higher than that of the wild strain. Fourier transform infrared spectroscopy of adapted cells suggested that a proteinaceous new cell surface component is synthesized by the adapted strain. Treatment of adapted cells with proteinase-K, resulted in complete loss of tolerance to copper, reduction in copper adsorption and hydrophobicity of the adapted cells. These observations strongly suggest a role played by cell surface modifications of Thiobacillus ferrooxidans in imparting the copper tolerance to the cells and bioleaching of sulphide minerals.

Flow and heat transfer in a stagnation-point flow over a stretching sheet with a magnetic field

The flow and heat transfer problem in the boundary layer induced by a continuous moving surface is important in many manufacturing processes in industry such as the boundary layer along material handling conveyers, the aerodynamic extrusion of plastic sheet, the cooling of an infinite metalic plate in a cooling bath (which may also be electrolyte). Glass blowing, continuous casting and spinning of fibres also involve the flow due to a stretching surface. Sakiadis [1] was the first to study the flow induced by a semi-infinite moving wall in an ambient fluid. On the other hand, Crane [2] first studied the flow over a linearly stretching sheet in an ambient fluid. Subsequently, Crane [3] also investigated the corresponding heat transfer problem. Since then several authors [4-8] have studied various aspects of this problem such as the effects of mass transfer, variable wall temperature, constant heat flux, magnetic field etc. Recently, Andersson [9] has obtained an exact solution of the Navier-Stokes equations for the MHD flow over a linearly stretching sheet in an ambient fluid. Also Chiam [10] has studied the heat transfer with variable thermal conductivity on a stretching sheet when the velocities of the sheet and the free stream are equal.