k-sets and random hulls

We re-examine the probabilistic analysis of Clarkson and Shor [5] involvingk-sets of point sets and related structures. By studying more carefully the equations that they derive, we are able to obtain refined analysis of these quantities, which lead to a collection of interesting relationships involvingk-sets, convex hulls of random samples, and generalizations of these constructs.Work on this paper has been supported by Office of Naval Research Grant N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Necessary and sufficient conditions for hyperplane transversals

We prove that a finite family ={B ₁,B ₂, ...,B _n } of connected compact sets in ^d has a hyperplane transversal if and only if for somek there exists a set of pointsP={p ₁,p ₂, ...,p _n } (i.e., ak-dimensional labeling of the family) which spans ^k and everyk+2 sets of are met by ak-flat consistent with the order type ofP. This is a common generalization of theorems of Hadwiger, Katchalski, Goodman-Pollack and Wenger.Supported in part by NSF grant DMS-8501947 and CCR-8901484, NSA grant MDA904-89-H-2030, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648.Supported by the National Science and Engineering Research Council of Canada and DIMACS.     

Morphisms of projective geometries and semilinear maps

Morphisms between projective geometries are introduced; they are partially defined maps satisfying natural geometric conditions. It is shown that in the arguesian case the morphisms are exactly those maps which in terms of homogeneous coordinates are described by semilinear maps. If one restricts the considerations to automorphisms (collineations) one recovers the so-called fundamental theorem of projective geometry, cf. Theorem 2.26 in [2].Supported by a grant from the Fonds National Suisse de la Recherche Scientifique.     

Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m ^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n ^1/2–1/2d(logn)^1+1/2d ). Also if any subcollection ofm sets of partitions the points into at mostO(m ^d) classes, then there is a coloring with discrepancy at mostO(n ^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

There are uncountably many universal topological planes

We prove the existence of uncountably many nonisomorphic topological projective planes, each universal in the sense that it contains an isomorphic copy of every pseudoline arrangement.     

Inequalities involving two simplexes

In this paper, we establish some geometric inequalities for two n-dimensional simplexes in the n-dimensional Euclidean space Eⁿ.This work is supported by the Hunan Provincial Science Foundation, P. R. China. S. Mingbao is a doctorate candidate of Nanjing University of Science and Technology.     

Triangles in space or building (and analyzing) castles in the air

We show that the total combinatorial complexity of all non-convex cells in an arrangement ofn (possibly intersecting) triangles in 3-space isO(n ^7/3 logn) and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement and an alternative less efficient, but still subcubic algorithm for calculating all non-convex cells, analyze some special cases of the problem where improved bounds (and faster algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.Work on this paper by the first author has been supported by an AT&T Bell Laboratories PhD Scholarship. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, the IBM Corporation, and by a research grant from the NCRD — the Israeli National Council for Research and Development. A preliminary version of this paper has appeared inProc. 4th ACM Symp. on Computational Geometry, Urbana, Illinois, 1988.     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

Two Remarks Concerning Balanced Matroids

The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following examples are exhibited: (a) a class of “sparse” paving matroids that are balanced, but at the same time rich enough combinatorially to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is likely to be computationally intractable. * The work described here was supported by the grant “Sharper analysis of randomised algorithms” from the UK Engineering and Physical Sciences Research Council.     

Upward planarity testing

Acyclic digraphs, such as the covering digraphs of ordered sets, are usually drawn upward, i.e., with the edges monotonically increasing in the vertical direction. A digraph is upward planar if it admits an upward planar drawing. In this survey paper, we overview the literature on the problem of upward planarity testing. We present several characterizations of upward planarity and describe upward planarity testing algorithms for special classes of digraphs, such as embedded digraphs and single-source digraphs. We also sketch the proof of NP-completeness of upward planarity testing.Research supported in part by the National Science Foundation under grant CCR-9423847.     

A non-analytic proof of the newman—znám result for disjoint covering systems

A direct combinatorial proof is given to a generalization of the fact that the largest modulusN of a disjoint covering system appears at leastp times in the system, wherep is the smallest prime dividingN. The method is based on geometric properties of lattice parallelotopes. This research was supported by grant 85-00368 from the United States-Is rael Binational Science Foundation, Jerusalem, Israel.     

An upper bound for the cardinality of ans-distance subset in real euclidean space,II

It is shown that ifX is ans-distance subset inR ^d , then |X|≦( _s ^d+s ). Supported in part by NSF grant MCS7903128 A01. Supported in part by NSF grant MCS.     

Crossing families

Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two setsA andB of points in the plane are mutually avoiding if no line subtended by a pair of points inA intersects the convex hull ofB, and vice versa. We show that any set ofn points in general position contains a pair of mutually avoiding subsets each of size at least . As a consequence we show that such a set possesses a crossing family of size at least , and describe a fast algorithm for finding such a family.Research supported in part by DARPA grant N00014-89-J-1988, Air Force AFOSR-89-0271, NSF grant DMS-8606225, and an ONR graduate fellowship. Further, part of this work was conducted at and supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC8809648.     

Optimality conditions for non-finite valued convex composite functions

Burke (1987) has recently developed second-order necessary and sufficient conditions for convex composite optimization in the case where the convex function is finite valued. In this note we present a technique for reducing the infinite valued case to the finite valued one. We then use this technique to extend the results in Burke (1987) to the case in which the convex function may take infinite values. We conclude by comparing these results with those established by Rockafellar (1989) for the piecewise linear-quadratic case.Dedicated to the memory of Robin W. ChaneyResearch supported in part by the National Science Foundation under grants DMS-8602399 and DMS-8803206, and by the Air Force Office of Scientific Research under grant ISSA-860080.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under grant OGP41983.     

The prison yard problem

Given a polygon II withn vertices whose sides arewalls. Guards, located at vertices can see all directions, but cannot see beyond walls. We prove that at most [n/2] guards suffice to see everywhere the whole plane. If II is not convex, then [n/2] suffice.The research was done while this author visited the Department of Mathematics at Rutgers University. Research supported in part by the Hungarian National Science Foundation under grant No. 1812Supported in part by NSF grant DMS 86-06225 and AF grant OSR-86-0078     

An upper bound for the cardinality of ans-distance subset in real euclidean space

IfX is ans-distance subset inR ^d , then |X|<( _s ^d+s )+( _s-1 ^d+s-1 . Supported in part by NSF grant MCS—7903128 (OSURF 711977).     

An acyclicity theorem for cell complexes ind dimension

LetC be a cell complex ind-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope ind+ 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces ofC with respect to any fixed viewpointx is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.Research reported in this paper was supported by the National Science Foundation under grant CCR-8714565     

On triangulations of the convex hull ofn points

A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex. This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347. This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347 Dedicated to Paul Erdős on his seventieth birthday     

Unitals in Topological Affine Translation Planes Need Not Be Strictly Convex

We study the relationship of two incidence geometric convexity notions, namely, ovoids in real affine spaces and compact unitals of codimension 1 in topological affine translation planes. In [3] we showed that every ovoid in a translation plane is a unital, and we asked if the converse is true. Here we introduce the notion of a shell, which is distinctly weaker than that of an ovoid and still implies the unital property if the translation plane is properly chosen (and the shell is not too degenerate). We give an explicit example of a shell that is not an ovoid. The question remains whether or not conversely, every compact unital of codimension 1 in a translation plane is a shell.This paper was written while the third author was supported by a grant from DFG and TÜBITAK.Received March 12, 2002 Published online November 18, 2002     

A projective characterisation of ellipsoids by isotropy

In projective geometry, ellipsoids may be characterised by a property of isotropy about a single point. The author wishes to thank Rainer L?wen for advice on the presentation of the proof.