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 .

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Probing the Neutral Edge Modes in Transport across a Point Contact via Thermal Effects in the Read-Rezayi Non-Abelian Quantum Hall States

Non-Abelian quantum Hall states are characterized by the simultaneous appearance of charge and neutral gapless edge modes, with the structure of the latter being intricately related to the existence of bulk quasiparticle excitations obeying non-Abelian statistics. Here we propose a scenario for detecting the neutral modes by having two point contacts in series separated by a distance set by the thermal equilibration length of the charge mode. We show that by using the first point contact as a heating device, the excess charge noise measured at the second point contact carries a nontrivial signature of the presence of the neutral mode. We also obtain explicit expressions for the thermal conductance and corresponding Lorentz number for transport across a quantum point contact between two edges held at different temperatures and chemical potentials.

An on-line algorithm for the location of cross point faults in programmable logic arrays

An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the algorithm is the determination of a fault set corresponding to the response obtained for a failed test. For the apparently small number of faults in this set, all other tests are generated and a fault table is formed. Subsequently, an adaptive procedure is used to diagnose the fault. Functional equivalence test is carried out to determine the actual fault class if the adaptive testing results in a set of faults with identical tests. The large amount of computation time and storage required in the determination, a priori, of all the fault equivalence classes or in the construction of a fault dictionary are not needed here. A brief study of functional equivalence among the cross point faults is also made.

An On-Line Algorithm for the Location of Cross Point Faults in Programmable Logic Arrays

An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the valgorithm is the determination of a fault set corresponding to the response obtained for a failed test. For the apparently small number of faults in this set, all other tests are generated and a fault table is formed. Subsequently, an adaptive procedure is used to diagnose the fault. Functional equivalence test is carried out to determine the actual fault class if the adaptive testing results in a set of faults with identical tests. The large amount of computation time and storage required in the determination, a priori, of all the fault equivalence classes or in the construction of a fault dictionary are not needed here. A brief study of functional equivalence among the cross point faults is also made.

Uniformity of film thickness on rotating planetary planar substrates

For the purposes of obtaining a number of components with nearly identical thickness distributions over the substrate area and of minimizing the inhomogeneities of the film, it is logical to presume that a substrate rotating on its own axis and revolving around another axis will give more uniformity in film thickness than a substrate only revolving around one axis. In relation to the practical applications, an investigation has been undertaken to study the refinement that can be achieved by using a planar planetary substrate holder. It is shown theoretically that the use of the planetary substrate holder under ideal conditions of source and geometry does not offer any further improvement in uniformity of thickness over the conventional rotary work-holder. It is also shown that the geometrical parameters alone have little influence over the uniformity achieved on a planetary substrate, because of the complex cyclidal motion of any point on it. However, for any given geometry, a non-integral speed ratio of the planetary substrate and the work-holder shows considerably less variation in thickness over the substrate area.

Wigner distributions for finite-state systems without redundant phase-point operators

We set up Wigner distributions for N-state quantum systems following a Dirac-inspired approach. In contrast to much of the work in this study, requiring a 2N x 2N phase space, particularly when N is even, our approach is uniformly based on an N x N phase-space grid and thereby avoids the necessity of having to invoke a `quadrupled' phase space and hence the attendant redundance. Both N odd and even cases are analysed in detail and it is found that there are striking differences between the two. While the N odd case permits full implementation of the marginal property, the even case does so only in a restricted sense. This has the consequence that in the even case one is led to several equally good definitions of the Wigner distributions as opposed to the odd case where the choice turns out to be unique.

A geometric approach for determining inner and exterior boundaries of workspaces of planar manipulators

In this paper a method to determine the internal and external boundaries of planar workspaces, represented with an ordered set of points, is presented. The sequence of points are grouped and can be interpreted to form a sequence of curves. Three successive curves are used for determining the instantaneous center of rotation for the second one of them. The two extremal points on the curve with respect to the instantaneous center are recognized as singular points. The chronological ordering of these singular points is used to generate the two envelope curves, which are potentially intersecting. Methods have been presented in the paper for the determination of the workspace boundary from the envelope curves. Strategies to deal with the manipulators with joint limits and various degenerate situations have also been discussed. The computational steps being completely geometric, the method does not require the knowledge about the manipulator's kinematics. Hence, it can be used for the workspace of arbitrary planar manipulators. A number of illustrative examples demonstrate the efficacy of the proposed method.

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.