An Improved Bound for Joints in Arrangements of Lines in Space

Let L be a set of n lines in space. A joint of L is a point in R³ where at least three non-coplanar lines meet. We show that the number of joints of L is O(n^112/69 log^6/23n)=O(n^1.6232), improving the previous bound O(n^1.643) of Sharir.     

Monotone Paths in Line Arrangements with a Small Number of Directions

We give subquadratic bounds on the maximum length of an x-monotone path in an arrangement of n lines with at most C log log n directions, where C is a suitable constant. For instance, the maximum length of an x-monotone path in an arrangement of n lines having at most ten slopes is O(n^67/34). In particular, we get tight estimates for the case of lines having at most five directions, by showing that previous constructions—(n^3/2) for arrangements with four slopes and (n^5/3) for arrangements with five slopes—due to Sharir and Matousek, respectively, are (asymptotically) best possible.     

Incidences between Points and Circles in Three and Higher Dimensions

We show that the number of incidences between m distinct points and n distinct circles in ^d, for any d 3, is O(m^6/11n^9/11(m³/n)+m^2/3n^2/3+m+n), where (n)=(log n)^O((n))2 and where (n) is the inverse Ackermann function. The bound coincides with the recent bound of Aronov and Sharir, or rather with its slight improvement by Agarwal et al., for the planar case. We also show that the number of incidences between m points and n unrestricted convex (or bounded-degree algebraic) plane curves, no two in a common plane, is O(m^4/7n^17/21+m^2/3n^2/3+m+n), in any dimension d 3. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space and the lower bound for the number of distinct distances in a set of n points in 3-space. Another application is an improved bound for the number of incidences (or, rather, containments) between lines and reguli in three dimensions. The latter result has already been applied by Feldman and Sharir to obtain a new bound on the number of joints in an arrangement of lines in three dimensions.     

On blocking sets of quadrics

We determine the three smallest blocking sets with respect to lines of the quadric Q(2n, q) withn 3 and the two smallest blocking sets with respect to lines of the quadric Q⁺(2n+1,q) withn 2. These results will be used in a forthcoming paper for determining the smallest blocking sets with respect to higher dimensional subspaces in the quadrics Q(2n, q) and Q⁺(2n+ 1, q).     

Combinatorial complexity bounds for arrangements of curves and spheres

We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is (m ^2/3 n ^2/3 +n), and that it isO(m ^2/3 n ^2/3 (n) +n) forn unit-circles, where(n) (and later(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m ^3/5 n ^4/5 (n) +n). The same bounds (without the(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m ^4/7 n ^9/7 (m, n) +n ²), in general, andO(m ^3/4 n ^3/4 (m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m ^3/2 (m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.The research of the second author was supported by the National Science Foundation under Grant CCR-8714565. Work by the fourth 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 and 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 in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988.     

The number of connected sparsely edged graphs. III. Asymptotic results

The number of connected graphs on n labeled points and q lines (no loops, no multiple lines) is f(n,q). In the first paper of this series I showed how to find an (increasingly complicated) exact formula for f(n,n+k) for general n and successive k. The method would give an asymptotic approximation to f(n,n+k) for any fixed k as n → ∞. Here I find this approximation when k = o(n^1/3), a much more difficult matter. The problem of finding an approximation to f(n,q) when q > n + Cn^1/3 and (2 q/n) - log n → - ∞ is open.     

On Constants for Cuttings in the Plane

A theorem of Chazelle and Friedman with numerous applications in combinatorial and computational geometry asserts that for any set L of n lines in the plane and for any parameter r>1 there exists a subdivision of the plane into at most Cr ² (possibly unbounded) triangles, C a constant, such that the interior of each triangle is intersected by at most n/r lines of L . (Such a subdivision is called a (1/r) -cutting for L .) We give upper and lower bounds on the constant C . We also consider the canonical triangulation of the arrangement of a random sample of r lines from L . Although this typically is not a (1/r) -cutting, the expectation of the k th degree average of the number of lines intersecting a triangle is O(n/r) for any fixed k . We estimate the constant of proportionality in this result. Received October 1, 1996, and in revised form September 25, 1997.     

Almost every 2-SAT function is unate

Bollobás, Brightwell and Leader [2] showed that there are at most 2-SAT functions on n variables, and conjectured that in fact the number of 2-SAT functions on n variables is . We prove their conjecture. As a corollary of this, we also find the expected number of satisfying assignments of a random 2-SAT function on n variables. We also find the next largest class of 2-SAT functions and show that if k = k(n) is any function with k(n) < n ^1/4 for all sufficiently large n, then the class of 2-SAT functions on n variables which cannot be made unate by removing 25k variables is smaller than for all sufficiently large n.     

Flag-Transitive 2-Designs Arising from Line-Spreads in PG(2n-1,2)

A Singer cycle in GL(n,q) is an element of order q permuting cyclically all the nonzero vectors. Let be a Singer cycle in GL(2n,2). In this note we shall count the number of lines in PG (2n-1,2) whose orbit under the subgroup of index 3 in the Singer group is a spread. The lines constituting such a spread are permuted cyclically by the group ³, hence gives rise to a flag-transitive 2-(2²ⁿ ,4,1) design.     

The order aspect of the fuzzy real line

It is the purpose of this paper to put the fuzzy real line in a setting which proves to be advantageous to a more fundamental study of that space.Actually there are three different fuzzy real lines to be found in the literature, mainly defined by U. Höhle in [1], [2] and by B. Hutton in [4], [5], and a fourth one shall be added in this work.The main result of this paper is the fact that three of the four spaces are homeomorphic to fuzzy topological spaces the underlying sets of which are, in each case, the probability measures on , and the fuzzy (resp. quasi fuzzy and translation-closed fuzzy) topologies of which are determined by the left and right sections of a canonical fuzzy extension of the strict order relation on . From this it will follow very fundamentally that it is the order of , and not the topology, which determines the fuzzy real line.     

Interpolation and Parallel Lines

Here we consider 3 interpolation problems for homogeneous polynomials in n n + 1 variables (i.e. for zero-dimensional subschemes Z of Pⁿ) in which the scheme Z is contained in a “ small number ” of “ parallel lines ”; here a finite union D₁ ∪ … ∪ D _x ? Pⁿ of lines is called a set of parallel lines if there is P ∈ Pⁿ such that P ∈ D _i for all i.     

A and the vanishing topology of discriminants

Summary Suppose thatf: ⁿ , 0 ^p , 0 is finitely -determined withnp. We define a Milnor fiber for the discriminant off; it is the discriminant of a stabilization off. We prove that this discriminant Milnor fiber has the homotopy type of a wedge of spheres of dimensionp–1, whose number we denote byµ (f). One of the main theorems of the paper is a = type result: if (n, p) is in the range of nice dimensions in the sense of Mather, then -codium,with equality iff is weighted homogeneous. Outside the nice dimensions we obtain analogous formulae with correction terms measuring the presence of unstable but topologically stable germs in the stabilization. These results are further extended to nonlinear sections of free divisors.Oblatum 15-VIII-1990Partially supported by a grant from the National Science Foundation and a Fullbright Fellowship     

Line Transversals to Disjoint Balls

We prove that the set of directions of lines intersecting three disjoint balls in ℝ³ in a given order is a strictly convex subset of . We then generalize this result to n disjoint balls in ℝ ^d . As a consequence, we can improve upon several old and new results on line transversals to disjoint balls in arbitrary dimension, such as bounds on the number of connected components and Helly-type theorems.     

Proper 2-Covers of PG(3,q), q Even

A k-cover of =PG(3q) is a set S of lines of such that every point is on exactly k lines of S. S is proper if it contains no spread. The existence of proper k-covers of is necessary for the existence of maximal partial packings of q ²+q+1–k spreads of . Here we give the first construction of proper 2-packings of PG(3,q) with q even; for q odd these have been constructed by Ebert.     

Geodesics in Heisenberg Groups

We obtain equations of geodesic lines in Heisenberg groups H²ⁿ⁺¹and prove that the ideal boundary of the Heisenberg group H²ⁿ⁺¹is a sphere S^2n-1with a natural CR-structure and corresponding Carnot-Carathéodory metric, i.e. it is a one-point compactification of the Heisenberg group H^2n-1of the next dimension in a row.     

An inequality for generalized hexagons

We show that a generalized hexagon withs + 1 points on a line andt + 1 lines through a point satisfies s=1 orts ³.     

Partitioning arrangements of lines I: An efficient deterministic algorithm

In this paper we consider the following problem: Given a set ofn lines in the plane, partition the plane intoO(r ²) triangles so that no triangle meets more thanO(n/r) lines of . We present a deterministic algorithm for this problem withO(nr logn/r) running time, where is a constant <3.33.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th Annual Symposium on Computational Geometry, 1989, pp. 11–22.     

On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

The representation of integers by binary additive forms

Let a, b and n be integers with 3. We show that, in the sense of natural density, almost all integers represented by the binary form axⁿ – byⁿ are thus represented essentially uniquely. By exploiting this conclusion, we derive an asymptotic formula for the total number of integers represented by such a form. These conclusions augment earlier work of Hooley concerning binary cubic and quartic forms, and generalise or sharpen work of Hooley, Greaves, and Skinner and Wooley concerning sums and differences of two nth powers.     

Triangles in arrangements of lines

A set of n nonconcurrent lines in the projective plane (called an arrangment) divides the plane into polygonal cells. It has long been a problem to find a nontrivial upper bound on the number of triangular regions. We show that $\text{5}\text{12}\text{n(n ? 1)}$ is such a bound. We also show that if no three lines are concurrent, then the number of quadrilaterals, pentagons and hexagons is at least cn².