Lattice polygons with two interior lattice points

A lattice point in the plane is a point with integer coordinates. A lattice segment is a line segment whose endpoints are lattice points. A lattice polygon is a simple polygon whose vertices are lattice points. We find all convex lattice polygons in the plane up to equivalence with two interior lattice points.     

Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem

An interior point method defines a search direction at each interior point of the feasible region. The search directions at all interior points together form a direction field, which gives rise to a system of ordinary differential equations (ODEs). Given an initial point in the interior of the feasible region, the unique solution of the ODE system is a curve passing through the point, with tangents parallel to the search directions along the curve. We call such curves off-central paths. We study off-central paths for the monotone semidefinite linear complementarity problem (SDLCP). We show that each off-central path is a well-defined analytic curve with parameter μ ranging over (0, ∞) and any accumulation point of the off-central path is a solution to SDLCP. Through a simple example we show that the off-central paths are not analytic as a function of and have first derivatives which are unbounded as a function of μ at μ = 0 in general. On the other hand, for the same example, we can find a subset of off-central paths which are analytic at μ = 0. These “nice” paths are characterized by some algebraic equations. This research was done during the author’s PhD study at the Department of Mathematics, NUS and as a Research Engineer at the NUS Business School.     

Existence of second order discretizations on irregular mesh

We give the necessary and sufficient conditions to obtain a difference formula of order two on an arbitrary distribution of mesh points. We also show how to form a 6 point computational cell in the physical plane if the mesh is generated by a boundary fitted coordinate generation procedure.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

Simply connected orthogonal polygons as unions of two orthogonally starshaped sets

Let S be a simply connected orthogonal polygon in the plane. The set S is a union of two sets which are starshaped via staircase paths (i.e., orthogonally starshaped) if and only if for every three points of S, at least two of these points see (via staircase paths) a common point of S. Moreover, the simple connectedness condition cannot be deleted.     

Extrapolation of Nyström Solutions of Boundary Integral Equations on Non-Smooth Domains

The interior Dirichlet problem for Laplace's equation on a plane polygonal region $\Omega$ with boundary $\Gamma$ may be reformulated as a second kind integral equation on $\Gamma$. This equation may be solved by the Nyström method using the composite trapezoidal rule. It is known that if the mesh has $O(n)$ points and is graded appropriately, then $O(1/n^2)$ convergence is obtained for the solution of the integral equation and the associated solution to the Dirichlet problem at any $x\in \Omega$. We present a simple extrapolation scheme which increases these rates of convergence to $O(1/n^4)$ .     

On the existence of a point subset with three or five interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let h(k) be the smallest integer such that every point set in the plane, no three collinear, with at least h(k) interior points, has a subset with k or k + 2 interior points of P. We prove that h(3) = 8.     

Stress recovery procedure for solving boundary value problems in the mechanics of a deformable solid by the finite element method

A stress recovery procedure, based on the determination of the forces at the mesh points using a stiffness matrix obtained by the finite element method for the variational Lagrange equation, is described. The vectors of the forces reduced to the mesh points are constructed for the known stiffness matrices of the elements using the displacements at the mesh points found from the solution of the problem. On the other hand, these mesh point forces are determined in terms of the unknown forces distributed over the surface of an element and given shape functions. As a result, a system of Fredholm integral equations of the first kind is obtained, the solution of which gives these distributed forces. The stresses at the mesh points are determined for the values of these forces found on the surfaces of the finite element mesh (including at the mesh points) using the Cauchy relations, which relate the forces, stresses and the normal to the surface. The special features of the use of the stress recovery procedure are demonstrated for a plane problem in the linear theory of elasticity.     

Which Crossing Number Is It Anyway?

A drawing of a graph G is a mapping which assigns to each vertex a point of the plane and to each edge a simple continuous arc connecting the corresponding two points. The crossing number of G is the minimum number of crossing points in any drawing of G. We define two new parameters, as follows. The pairwise crossing number (resp. the odd-crossing number) of G is the minimum number of pairs of edges that cross (resp. cross an odd number of times) over all drawings of G. We prove that the largest of these numbers (the crossing number) cannot exceed, twice the square of the smallest (the odd-crossing number). Our proof is based on the following generalization of an old result of Hanani, which is of independent interest. Let G be a graph and let E₀ be a subset of its edges such that there is a drawing of G, in which every edge belonging to E₀ crosses any other edge an even number of times. Then g can be redrawn so that the elements of E₀ are not involved in any crossing. Finally, we show that the determination of each of these parameters is an NP-hard problem and it is NP-complete in the case of the crossing number and the odd-crossing number.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

On Polygons Excluding Point Sets

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that ${B\cup R}$ is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K = K(l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k ≥ K. Some other related problems are also considered.     

The 2D‐directed spanning forest is almost surely a tree

We consider the Directed Spanning Forest (DSF) constructed as follows: given a Poisson point process N on the plane, the ancestor of each point is the nearest vertex of N having a strictly larger abscissa. We prove that the DSF is actually a tree. Contrary to other directed forests of the literature, no Markovian process can be introduced to study the paths in our DSF. Our proof is based on a comparison argument between surface and perimeter from percolation theory. We then show that this result still holds when the points of N belonging to an auxiliary Boolean model are removed. Using these results, we prove that there is no bi‐infinite paths in the DSF. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Solving real-world linear ordering problems using a primal-dual interior point cutting plane method

Cutting plane methods require the solution of a sequence of linear programs, where the solution to one provides a warm start to the next. A cutting plane algorithm for solving the linear ordering problem is described. This algorithm uses the primaldual interior point method to solve the linear programming relaxations. A point which is a good warm start for a simplex-based cutting plane algorithm is generally not a good starting point for an interior point method. Techniques used to improve the warm start include attempting to identify cutting planes early and storing an old feasible point, which is used to help recenter when cutting planes are added. Computational results are described for some real-world problems; the algorithm appears to be competitive with a simplex-based cutting plane algorithm.Research partially supported by ONR Grant number N00014-90-J-1714.     

Singular Points Near an X_0-breaking Double Singular Fold Point in Z_2-symmetric Nonlinear Equations

ＳｉｎｇｕｌａｒＰｏｉｎｔｓＮｅａｒａｎＸ_０－ｂｒｅａｋｉｎｇＤｏｕｂｌｅＳｉｎｇｕｌａｒＦｏｌｄＰｏｉｎｔｉｎＺ_２－ｓｙｍｍｅｔｒｉｃＮｏｎｌｉｎｅａｒＥｑｕａｔｉｏｎｓＳｕＹｉ（苏毅）ａｎｄＷｕｗｅｉ（吴微）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅ...     

On the Central Paths in Symmetric Cone Programming

This paper is devoted to the study of optimal solutions of symmetric cone programs by means of the asymptotic behavior of central paths with respect to a broad class of barrier functions. This class is, for instance, larger than that typically found in the literature for semidefinite positive programming. In this general framework, we prove the existence and the convergence of primal, dual and primal–dual central paths. We are then able to establish concrete characterizations of the limit points of these central paths for specific subclasses. Indeed, for the class of barrier functions defined at the origin, we prove that the limit point of a primal central path minimizes the corresponding barrier function over the solution set of the studied symmetric cone program. In addition, we show that the limit points of the primal and dual central paths lie in the relative interior of the primal and dual solution sets for the case of the logarithm and modified logarithm barriers.     

On the interior lattice points of convex lattice 11-gon

A lattice point in the plane is a point with integer coordinates. A lattice polygon K is a polygon whose vertices are lattice points. In this note we prove that any convex lattice 11-gon contains at least 15 interior lattice points.     

Degenerate Crossing Numbers

Let G be a graph with n vertices and e≥4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p, then they properly cross one another at p. It is shown that the number of crossing points, counted without multiplicity, is at least constant times e and that the order of magnitude of this bound cannot be improved. If, in addition, two edges are allowed to cross only at most once, then the number of crossing points must exceed constant times (e/n)⁴. The research of J. Pach was supported by NSF grant CCF-05-14079 and by grants from NSA, PSC-CUNY, BSF, and OTKA-K-60427. The research of G. Tóth was supported by OTKA-K-60427.     

More on planar point subsets with a specified number of interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let g(k) be the smallest integer such that every set P of points in the plane with no three collinear points and with at least g(k) interior points has a subset containing precisely k interior point of P. We prove that g(k) ≥ 3k for k ≥ 3, which improves the known result that g(k) ≥ 3k ? 1 for k ≥ 3.     

Gaps in Convex Disc Packings with an Application to 1-Steiner Minimum Trees

 We show that if six translates of a convex disc C all touch C, and no two of the translates have interior points in common, then there are never more than two gaps, i.e., consecutive non-touching pairs of translates. We also characterize the configurations where there are two, one or no gaps. This result is then applied to show that the Steiner point in a 1-Steiner Minimum Tree in a normed plane has degree at most five if the unit ball is not an affine regular hexagon (where Steiner points of degree six exist).     

A Middle School Extension of Pick's Theorem to Areas of Nonsimple Closed Polygonal Regions

The author has extended Pick's theorem for simple closed polygonal regions to unions of simple closed polygonal regions–a topic that is manageable for middle grade students. From sets of data including numbers of boundary points and numbers of interior points, students are guided to discover Pick's theorem. Additionally, with the author's creation of crossing points, Pick's theorem is extended to include areas of other polygonal regions. The article is developed along lines of the 1989 Standards of the NCTM in the use of data tables which lead to the discovery of a formula.