Applications of a semi-dynamic convex hull algorithm

We obtain new results for manipulating and searching semi-dynamic planar convex hulls (subject to deletions only), and apply them to derive improved bounds for two problems in geometry and scheduling. The new convex hull results are logarithmic time bounds for set splitting and for finding a tangent when the two convex hulls are not linearly separated. Using these results, we solve the following two problems optimally inO(n logn) time: (1) [matching] givenn red points andn blue points in the plane, find a matching of red and blue points (by line segments) in which no two edges cross, and (2) [scheduling] givenn jobs with due dates, linear penalties for late completion, and a single machine on which to process them, find a schedule of jobs that minimizes the maximum penalty.     

Bichromatic and Equichromatic Lines in ℂ2 and ℝ2

Let G and R each be a finite set of green and red points, respectively, such that |G|=n, |R|=n−k, G∩R=∅, and the points of G∪R are not all collinear. Let t be the total number of lines determined by G∪R. The number of equichromatic lines (a subset of bichromatic) is at least (t+2n+3−k(k+1))/4. A slightly weaker lower bound exists for bichromatic lines determined by points in ℂ². For sufficiently large point sets, a proof of a conjecture by Kleitman and Pinchasi is provided. A lower bound of (2t+14n−k(3k+7))/14 is demonstrated for bichromatic lines passing through at most six points. Lower bounds are also established for equichromatic lines passing through at most four, five, or six points.     

A Cellular Triangle Containing a Specified Point

 Let P be a set of finite points in the plane in general position, and let x be a point which is not contained in any of the lines passing through at least two points of P. A line l is said to be a k-bisector if both of the two closed half-planes determined by l contain at least k points of P. We show that if any line passing through x is a -bisector and does not contain two or more points of P, then there exist three points P ₁, P ₂, P ₃ of P such that ΔP ₁ P ₂ P ₃ contains x and does not contain points of P in its interior, and such that each of the lines passing through two of them is a -bisector. Received: October 16, 1995 / Revised: October 16, 1996     

The Maximum Number of Edges in Geometric Graphs with Pairwise Virtually Avoiding Edges

Let G be a geometric graph on n vertices that are not necessarily in general position. Assume that no line passing through one edge of G meets the relative interior of another edge. We show that in this case the number of edges in G is at most 2n?3.     

Generalizing Ham Sandwich Cuts to Equitable Subdivisions

We prove a generalization of the famous Ham Sandwich Theorem for the plane. Given gn red points and gm blue points in the plane in general position, there exists an equitable subdivision of the plane into g disjoint convex polygons, each of which contains n red points and m blue points. For g=2 this problem is equivalent to the Ham Sandwich Theorem in the plane. We also present an efficient algorithm for constructing an equitable subdivision. Received February 19, 1999, and in revised form June 3, 1999. {\it Online publication August\/} 18, 2000.     

Sylvester–Gallai Theorem and Metric Betweenness

Sylvester conjectured in 1893 and Gallai proved some 40 years later that every finite set S of points in the plane includes two points such that the line passing through them includes either no other point of S or all other points of S. There are several ways of extending the notion of lines from Euclidean spaces to arbitrary metric spaces. We present one of them and conjecture that, with lines in metric spaces defined in this way, the Sylvester--Gallai theorem generalizes as follows: in every finite metric space there is a line consisting of either two points or all the points of the space. Then we present meagre evidence in support of this rash conjecture and finally we discuss the underlying ternary relation of metric betweenness.     

Quasi-random 2- colorings of point sets

Given an arbitrary set of N points on the plane, one can two-color the points red and blue in such a way that the difference of the numbers of red and blue points in any half-plane has absolute value less than N^1/4(log N)⁴. This is essentially best possible.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

Generalized convex kernels of simply connected <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> sets in the plane

Let D be a compact, simply connected subset of ℜ². Assume that every two points of D can be connected by a polygonal line with at most n edges within D. Then there is a point q ∈ D that can be connected to any other point in D by a polygonal line with at most n edges. This is best possible for all n.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi. Received 17 November 1997; in revised form 30 July 1998     

Unavoidable Configurations in Complete Topological Graphs

A topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by Jordan curves connecting the corresponding points, with the property that any two curves have at most one point in common. We define two canonical classes of topological complete graphs, and prove that every topological complete graph with n vertices has a canonical subgraph of size at least clog^1/8 n, which belongs to one of these classes. We also show that every complete topological graph with n vertices has a non-crossing subgraph isomorphic to any fixed tree with at most clog^1/6 n vertices.     

The Number of Generalized Balanced Lines

Let S be a set of r red points and b=r+2δ blue points in general position in the plane, with δ≥0. A line ℓ determined by them is balanced if in each open half-plane bounded by ℓ the difference between the number of blue points and red points is δ. We show that every set S as above has at least r balanced lines. The proof is a refinement of the ideas and techniques of Pach and Pinchasi (Discrete Comput. Geom. 25:611–628, 2001), where the result for δ=0 was proven, and introduces a new technique: sliding rotations.     

The Number of Cylindrical Shells

Given a set P of n points in three dimensions, a cylindrical shell (or zone cylinder) is formed by two circular cylinders with the same axis such that all points of P are between the two cylinders. We prove that the number of cylindrical shells enclosing P passing through combinatorially different subsets of P has size (n ³) and O(n ⁴) (the previously known bound was O(n ⁵)). As a consequence, the minimum enclosing shell can be found in O(n ⁴) time.     

The <Emphasis Type="Italic">k</Emphasis>-Centrum Straight-line Location Problem

A line is sought in the plane which minimizes the sum of the k largest (Euclidean) weighted distances from n given points. This problem generalizes the known straight-line center and median problems and, as far as the authors are aware, has not been tackled up to now. By way of geometric duality it is shown that such a line may always be found which either passes through two of the given points or lying at equal weighted distance from three of these. This allows construction of an algorithm to find all t-centrum lines for 1 ≤ t ≤ k in O((k + logn)n ³). Finally it is shown that both, the characterization of an optimal line and the algorithm, can be extended to any smooth norm.     

Some Bipartite Ramsey Numbers

Consider a complete bipartite graph K(s, s) with p = 2s points. Let each line of the graph have either red or blue colour. The smallest number p of points such that K(s, s) always contains red K(m, n) or blue K(m, n) is called bipartite Ramsey number denoted by rb(K(m, n), K(m, n)). In this paper, we show that

On the Erd s-diameter of sets

Let δ(n) denote the minimum diameter of a set of n points in the plane in which any two positive distances, if they are different, differ by at least one. Erd s conjectured that for n sufficiently big we have δ(n) = n − 1, the extremal configuration being n equidistant points on a line. In this note we prove an asymptotic version of this conjecture for the special case of sets which lie in a parallel half-strip.     

A two-parameter spectral theorem

Summary We study the characteristic set of a couple (A, B) of selfadjoint compact operators on a real Hilbert spaceH. We prove thatC is the union of a sequence of characteristic curvesC _n in the (, ) plane. Each curve is the analytic image of an open interval and it is either closed or it goes to infinity at both ends of the interval. Moreover, it may intersect either itself or other characteristic curves in an at most countable set of points, which may accumulate only at infinity. Finally, to each characteristic curve one can associate an analytic function E_n, which gives the eigenprojection onto the eigenspace attached to each point of the characteristic curve, except at the intersection points, where the eigenspace is the direct sum of the projection relevant to each branch passing through the point. The dimension of the eigenprojection is constant along each curve and it is called the multiplicity of the characteristic curve.     

Finiteness of the number of ends of minimal submanifolds in euclidean space

We prove a version of the well-known Denjoy-Ahlfors theorem about the number of asymptotic values of an entire function for properly immersed minimal surfaces of arbitrary codimension in ℝ ^N . The finiteness of the number of ends is proved for minimal submanifolds with finite projective volume. We show, as a corollary, that a minimal surface of codimensionn meeting anyn-plane passing through the origin in at mostk points has no morec(n, N)k ends.     

An Improvement to “A Note on Euclidean Ramsey Theory”

We characterize those subsets Y⊆ℝ ⁿ such that for every infinite X⊆ℝ ⁿ , there is a red/blue coloring of ℝ ⁿ having no monochromatic red set similar to X and no monochramtic blue set similar to Y.     

On edges crossing few other edges in simple topological complete graphs

We study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A topological graphT=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersection point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is simple if any two edges meet in at most one common point.Let h=h(n) be the smallest integer such that every simple topological complete graph on n vertices contains an edge crossing at most h other edges. We show that Ω(n^3/2)≤h(n)≤O(n²/log^1/4n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn².