Coloring copoints of a planar point set

To a set of n points in the plane, one can associate a graph that has less than n² vertices and has the property that k-cliques in the graph correspond vertex sets of convex k-gons in the point set. We prove an upper bound of 2^k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number. Constructions of Erd?s and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

On the Order Dimension of Convex Geometries

We study the order dimension of the lattice of closed sets for a convex geometry. We show that the lattice of closed subsets of the planar point set of Erd?s and Szekeres from 1961, which is a set of 2 ^n???2 points and contains no vertex set of a convex n-gon, has order dimension n???1 and any larger set of points has order dimension at least n.     

The Polytope of Non-Crossing Graphs on a Planar Point Set

For any set A of n points in ², we define a (3n - 3)-dimensional simple polyhedron whose face poset is isomorphic to the poset of non-crossing marked graphs with vertex set A, where a marked graph is defined as a geometric graph together with a subset of its vertices. The poset of non-crossing graphs on A appears as the complement of the star of a face in that polyhedron. The polyhedron has a unique maximal bounded face, of dimension 2n_i + n - 3 where n_i is the number of points of A in the interior of conv (A). The vertices of this polytope are all the pseudo-triangulations of A, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge. As a by-product of our construction we prove that all pseudo-triangulations are infinitesimally rigid graphs.     

Decompositions,Partitions, and Coverings with Convex Polygons and Pseudo-Triangles

We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k-gons in point sets.     

On the number of rectangulations of a planar point set

We investigate the number of different ways in which a rectangle containing a set of n noncorectilinear points can be partitioned into smaller rectangles by n (nonintersecting) segments, such that every point lies on a segment. We show that when the relative order of the points forms a separable permutation, the number of rectangulations is exactly the (n+1)st Baxter number. We also show that no matter what the order of the points is, the number of guillotine rectangulations is always the nth Schröder number, and the total number of rectangulations is O(n²⁰/n⁴).     

On degrees in random triangulations of point sets

We study the expected number of interior vertices of degree i in a triangulation of a planar point set S, drawn uniformly at random from the set of all triangulations of S, and derive various bounds and inequalities for these expected values. One of our main results is: For any set S of N points in general position, and for any fixed i, the expected number of vertices of degree i in a random triangulation is at least γiN, for some fixed positive constant γi (assuming that N>i and that at least some fixed fraction of the points are interior).We also present a new application for these expected values, using upper bounds on the expected number of interior vertices of degree 3 to get a new lower bound, Ω(N^2.4317), for the minimal number of triangulations any N-element planar point set in general position must have. This improves the previously best known lower bound of Ω(N^2.33).     

Area-efficient planar straight-line drawings of outerplanar graphs

It is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with n vertices admits a planar straight-line grid drawing with O(n²) area [H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica 10(1) (1990) 41-51; W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-148]. Unfortunately, there is a matching lower-bound of Ω(n²) on the area-requirements of the planar straight-line grid drawings of certain planar graphs. Hence, it is important to investigate important categories of planar graphs to determine if they admit planar straight-line grid drawings with o(n²) area.In this paper, we investigate an important category of planar graphs, namely, outerplanar graphs. We show that an outerplanar graph G with degree d admits a planar straight-line grid drawing with area O(dn^1.48) in O(n) time. This implies that if d=o(n^0.52), then G can be drawn in this manner in o(n²) area.     

Solving discrete systems of nonlinear equations

We study the existence problem of a zero point of a function defined on a finite set of elements of the integer lattice Zⁿ of the n-dimensional Euclidean space Rⁿ. It is assumed that the set is integrally convex, which implies that the convex hull of the set can be subdivided in simplices such that every vertex is an element of Zⁿ and each simplex of the triangulation lies in an n-dimensional cube of size one. With respect to this triangulation we assume that the function satisfies some property that replaces continuity. Under this property and some boundary condition the function has a zero point. To prove this we use a simplicial algorithm that terminates with a zero point within a finite number of iterations. The standard technique of applying a fixed point theorem to a piecewise linear approximation cannot be applied, because the ‘continuity property’ is too weak to assure that a zero point of the piecewise linear approximation induces a zero point of the function itself. We apply the main existence result to prove the existence of a pure Cournot-Nash equilibrium in a Cournot oligopoly model. We further obtain a discrete analogue of the well-known Borsuk-Ulam theorem and a theorem for the existence of a solution for the discrete nonlinear complementarity problem.     

Few distinct distances implies no heavy lines or circles

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set \(\mathcal{P}\) of n points determines o(n) distinct distances, then no line contains Ω(n ^7/8) points of \(\mathcal{P}\) and no circle contains Ω(n ^5/6) points of \(\mathcal{P}\).We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in [19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang [20].A significant difference between our approach and that of [19] (and of other related results) is that instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.     

Extremal problems on triangle areas in two and three dimensions

The study of extremal problems on triangle areas was initiated in a series of papers by Erd?s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.In the plane, our main result is an O(n44/19)=O(n^2.3158) upper bound on the number of unit-area triangles spanned by n points, which is the first breakthrough improving the classical bound of O(n7/3) from 1992. We also make progress in a number of important special cases. We show that: (i) For points in convex position, there exist n-element point sets that span Ω(nlogn) triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by n points is at most ; there exist n-element point sets (for arbitrarily large n) that span (6/π²−o(1))n² minimum-area triangles. (iii) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (iv) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are n-element point sets that span Ω(nlogn) minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds).In 3-space we prove an O(n17/7β(n))=O(n^2.4286) upper bound on the number of unit-area triangles spanned by n points, where β(n) is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, O(n8/3), is an old result of Erd?s and Purdy from 1971. We further show, for point sets in 3-space: (i) The number of minimum nonzero area triangles is at most n²+O(n), and this is worst-case optimal, up to a constant factor. (ii) There are n-element point sets that span Ω(n4/3) triangles of maximum area, all incident to a common point. In any n-element point set, the maximum number of maximum-area triangles incident to a common point is O(n4/3+ε), for any ε>0. (iii) Every set of n points, not all on a line, determines at least Ω(n2/3/β(n)) triangles of distinct areas, which share a common side.     

Off-line dynamic maintenance of the width of a planar point set

Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1990) 65-78. In this paper we present an efficient algorithm for the off-line dynamic maintenance of the width of a planar point set in the following restricted case: We are given a real parameter W and a sequence Σ=(σ₁,...,σ_n) of n insert and delete operations on a set S of points in ², initially consisting of n points, and we want to determine whether there is an i such that the width of S the ith operation is less than or equal to W. Our algorithm runs in time O(nlog³n) and uses O(n) space.     

The Asymptotic Number of Planar,Slim, Semimodular Lattice Diagrams

A lattice L is slim if it is finite and the set of its join-irreducible elements contains no three-element antichain. We prove that there exists a positive constant C such that, up to similarity, the number of planar diagrams of slim semimodular lattices of size n is asymptotically C · 2 ⁿ .     

Incremental and Decremental Maintenance of Planar Width

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^ε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^ε).     

A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing

Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in ?², there is a line ? such that in both line sets, for both halfplanes delimited by ?, there are $\sqrt{n}$ lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are $\sqrt{n/3}$ of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erd?s–Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to graph drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labeled lines that are universal for all n-vertex labeled planar graphs. In contrast, the main result by Pach and Toth (J. Graph Theory 46(1):39–47, 2004), has, as an easy consequence, that every set of n (unlabeled) lines is universal for all n-vertex (unlabeled) planar graphs.     

Asymptotic bounds for the number of convex n-ominoes

Unit squares having their vertices at integer points in the Cartesian plane are called cells. A point set equal to a union of n distinct cells which is connected and has no finite cut set is called an n-omino. Two n-ominoes are considered the same if one is mapped onto the other by some translation of the plane. An n-omino is convex if all cells in a row or column form a connected strip. Letting c(n) denote the number of different convex n-ominoes, we show that the sequence ((c(n))¹ⁿ: n=1,2,…) tends to a limit γ and γ=2.309138….     

Convex hull properties and algorithms

Convex hull (CH) is widely used in computer graphic, image processing, CAD/CAM, and pattern recognition. We investigate CH properties and derive new properties: (1) CH vertices’ coordinates monotonically increase or decrease, (2) The edge slopes monotonically decrease. Using these properties, we proposed two algorithms, i.e., CH algorithm for planar point set, and CH algorithm for two available CHs. The main ideas of the proposed algorithms are as follows. A planar point set is divided into several subsets by the extreme points, and vertices in these subsets are then separately calculated. During the computation, the CH properties are used to eliminate concave points. This can reduce the computational cost and then improves the speed. Our first algorithm can extract CH with O(nlogn) time, which is the lower bound of planar CH extraction, and the second algorithm can obtain CH with O(m+n) time at the worst case.     

Proper holomorphic embeddings of finitely connected planar domains into ℂ n

In this paper we consider proper holomorphic embeddings of finitely connected planar domains into ? ⁿ that approximate given proper embeddings on smooth curves. As a side result we obtain a tool for approximating a $\mathcal{C}^{\infty}$ diffeomorphism on a polynomially convex set in ? ⁿ by an automorphism of ? ⁿ that satisfies some additional properties along a real embedded curve.     

On the complement of the set of n-collinear points in PG(3, n)

Let ${S = (\mathcal{P}, \mathcal{L}, \mathcal{H})}$ be the finite planar space obtained from the 3-dimensional projective space PG(3, n) of order n by deleting a set of n-collinear points. Then, for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane or a punctured projective plane, and every line of S has size n or n + 1. In this paper, we prove that a finite planar space with lines of size n + 1 ? s and n + 1, (s ≥ 1), and such that for every point ${p\in S}$ , the quotient geometry S/p is either a projective plane of order n or a punctured projective plane of order n, is obtained from PG(3, n) by deleting either a point, or a line or a set of n-collinear points.