On the number of antipodal or strictly antipodal pairs of points in finite subsets ofR d,II

The paper is a continuation of [MM], namely containing several statements related to the concept of antipodal and strictly antipodal pairs of points in a subsetX ofR ^d , which has cardinalityn. The pointsx _i, x_jX are called antipodal if each of them is contained in one of two different parallel supporting hyperplanes of the convex hull ofX. If such hyperplanes contain no further point ofX, thenx _i, x_j are even strictly antipodal. We shall prove some lower bounds on the number of strictly antipodal pairs for givend andn. Furthermore, this concept leads us to a statement on the quotient of the lengths of longest and shortest edges of speciald-simplices, and finally a generalization (concerning strictly antipodal segments) is proved.Research (partially) supported by Hungarian National Foundation for Scientific Research, grant no. 1817     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

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.     

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     

Computing Hereditary Convex Structures

Color red and blue the n vertices of a convex polytope \(\mathcal{P}\) in ?³. Can we compute the convex hull of each color class in o(nlog?n) time? What if we have more than two colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of \(\mathcal{P}\) inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.     

The geometry of logconcave functions and sampling algorithms

The class of logconcave functions in ℝⁿ is a common generalization of Gaussians and of indicator functions of convex sets. Motivated by the problem of sampling from logconcave density functions, we study their geometry and introduce a technique for “smoothing” them out. These results are applied to analyze two efficient algorithms for sampling from a logconcave distribution in n dimensions, with no assumptions on the local smoothness of the density function. Both algorithms, the ball walk and the hit‐and‐run walk, use a random walk (Markov chain) to generate a random point. After appropriate preprocessing, they produce a point from approximately the right distribution in time O*(n⁴) and in amortized time O*(n³) if n or more sample points are needed (where the asterisk indicates that dependence on the error parameter and factors of log n are not shown). These bounds match previous bounds for the special case of sampling from the uniform distribution over a convex body.© 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Bichromatic Lines with Few Points

Given a set of n blue and n red points in the plane, not all on a line, it is shown that there exists a bichromatic line passing through at most two blue points and at most two red points. There does not necessarily exist a line passing through precisely one blue and one red point. This result is extended to the case when the number of blue and red points is not the same.     

Lower Bounds on Strip Discrepancy for Nonatomic Colorings

 A method of proof is given for obtaining lower bounds on strip discrepancy when the distributions do not have atoms. Partition the unit square into an chessboard of congruent square pixels, where n is even. Color of the pixels red, and the rest blue. For any convex set A, let be the difference between the amounts of red and blue areas in A. Under a technical local balance condition, we prove there must be a strip S, of width less than , for which , where c is a positive constant, independent of n and the coloring. The proof extends methods discovered by Alexander and further developed by Chazelle, Matoušek, and Sharir. Integral geometric notions figure prominently. (Received 21 September 1998; in final form 21 February 2000)     

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.     

Convex hulls of curves of genus one

Let C be a real nonsingular affine curve of genus one, embedded in affine n-space, whose set of real points is compact. For any polynomial f which is nonnegative on C(R), we prove that there exist polynomials fi with (mod IC) and such that the degrees deg(fi) are bounded in terms of deg(f) only. Using Lasserre?s relaxation method, we deduce an explicit representation of the convex hull of C(R) in Rn by a lifted linear matrix inequality. This is the first instance in the literature where such a representation is given for the convex hull of a nonrational variety. The same works for convex hulls of (singular) curves whose normalization is C. We then make a detailed study of the associated degree bounds. These bounds are directly related to size and dimension of the projected matrix pencils. In particular, we prove that these bounds tend to infinity when the curve C degenerates suitably into a singular curve, and we provide explicit lower bounds as well.     

Difference of two sets and estimation of clarke generalized Jacobian via quasidifferential

The notion of difference for two convex compact sets inR ⁿ , proposed by Rubinovet al, is generalized toR ^m×n . A formula of the difference for the two sets, which are convex hulls of a finite number of points, is developed. In the light of this difference, the relation between Clarke generalized Jacobian and quasidifferential, in the sense of Demyanov and Rubinov, for a nonsnooth function, is established. Based on the relation, the method of estimating Clarke generalized Jacobian via quasidifferential for a certain class of functions, is presented.     

Counting the onion

Iteratively computing and discarding a set of convex hulls creates a structure known as an “onion.” In this paper, we show that the expected number of layers of a convex hull onion for n uniformly and independently distributed points in a disk is Θ(n^2/3). Additionally, we show that in general the bound is Θ(n^2/(d+1)) for points distributed in a d‐dimensional ball. Further, we show that this bound holds more generally for any fixed, bounded, full‐dimensional shape with a nonempty interior. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

A combinatorial perspective on the Radon convexity theorem

Matroid-theoretic methods are employed to compute the number of complementary subsets of points of a set S whose convex hulls intersect (a number Radon proved to be nonzero when S has an affine dependency). This number is shown to be an invariant only of the dependence structure of S. Strict bounds are given depending on the cardinality and dimension of S and the number is related to other matroid invariants.     

A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.     

On ordinary points in arrangements

We show that in an arrangement ofn curves in the plane (or on the sphere) there are at leastn/2 points where precisely 2 curves cross (ordinary points). Furthermore there are at least (4/3)n triangular regions in the complex determined by the arrangement. Triangular regions and ordinary vertices are both connected with boundary vertices of certain distinguished subcomplexes. By analogy with rectilinear planar polygons we distinguish concave and convex vertices of these subcomplexes. Our lower bounds arise from lower bounds for convex vertices in the distinguished subcomplexes.     

Starshaped hypersurfaces¶and the mean curvature flow

Under the assumption of two a-priori bounds for the mean curvature, we are able to generalize a recent result due to Huisken and Sinestrari [8], valid for mean convex surfaces, to a much larger class. In particular we will demonstrate that these a-priori bounds are satisfied for a class of surfaces including meanconvex as well as starshaped surfaces and a variety of manifolds that are close to them. This gives a classification of the possible singularities for these surfaces in the case n= 2. In addition we prove that under certain initial conditions some of them become mean convex before the first singularity occurs. Received: 6 June 1997 / Revised version: 24 October 1997     

Starshaped hypersurfaces and the mean curvature flow

Under the assumption of two a-priori bounds for the mean curvature, we are able to generalize a recent result due to Huisken and Sinestrari [8], valid for mean convex surfaces, to a much larger class. In particular we will demonstrate that these a-priori bounds are satisfied for a class of surfaces including meanconvex as well as starshaped surfaces and a variety of manifolds that are close to them. This gives a classification of the possible singularities for these surfaces in the casen=2. In addition we prove that under certain initial conditions some of them become mean convex before the first singularity occurs.     

A theorem of ordered duality

We associate, to any ordered configuration of n points or ordered arrangement of n lines in the plane, a periodic sequence of permutations of [1, n] in a way which reflects the order and convexity properties of the configuration or arrangement, and prove that a sequence of permutations of [1, n] is associated to some configuration of points if and only if it is associated to some arrangement of lines. We show that this theorem generalizes the standard duality principle for the projective plane, and we use it to derive duals of several well-known theorems about arrangements, including a version of Helly's theorem for convex polygons.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.