Polyhedral line transversals in space

Algorithms are developed for determining if a set of polyhedral objects inR ³ can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total ofn vertices, we give anO(n ⁴ logn) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.     

Efficient piecewise-linear function approximation using the uniform metric

We given anO(n logn)-time method for finding a bestk-link piecewise-linear function approximating ann-point planar point set using the well-known uniform metric to measure the error, ε≥0, of the approximation. Our methods is based upon new characterizations of such functions, which we exploit to design an efficient algorithm using a plane sweep in “ε space” followed by several applications of the parametric-searching technique. The previous best running time for this problems wasO(n ²). This research was announced in preliminary form at the 10th ACM Symposium on Computational Geometry. The author was partially supported by the NSF and DARPA under Grant CCR-8908092, and by the NSF under Grants IRI-9116843 and CCR-9300079.     

Maximal arcs in designs

An (α,n)-arc in a 2-design is a set ofn points of the design such that any block intersects it in at most α points. For such an arc,n is bounded by 1+(r(α−1)/λ), with equality if and only if every block meets the arc in either 0 or α points. An (α,n) arc with equality in above is said to be maximal. A maximal block arc can be dually defined. This generalizes the notion of an oval (α=2) in a symmetric design due to Asmus and van Lint. The aim of this paper is to study the infinite family of possibly extendable symmetric designs other than the Hadamard design family and their related designs using maximal arcs. It is shown that the extendability corresponds to the existence of a proper family of maximal arcs. A natural duality between point and block arcs is established, which among other things implies a result of Cameron and van Lint that extendability of a given design in this family is equivalent to extendability of its dual. Similar results are proved for other related designs.     

n-point sets and graphs of functions

We prove that, for every n?2, there exists an n-point set (a plane set which hits every line in exactly n points) that is homeomorphic to the graph of a function from R to R; for n?4, there exist both 0-dimensional and 1-dimensional examples. This raises the question (which we do not answer) of whether n-point sets for different n's could be homeomorphic.     

The geometry of some two-character sets

A projective (n, d, w ₁, w ₂) _q set (or a two-character set for short) is a set of n points of PG(d − 1, q) with the properties that the set generates PG(d − 1, q) and that every hyperplane meets the set in either n − w ₁ or n − w ₂ points. Here geometric constructions of some two-character sets are given. The constructions mainly involve commuting polarities, symplectic polarities and normal line-spreads of projective spaces. Some information about the automorphism groups of such sets is provided.      

Blocking Visibility for Points in General Position

For a finite set P in the plane, let b(P) be the smallest possible size of a set Q, Q∩P=∅, such that every segment with both endpoints in P contains at least one point of Q. We raise the problem of estimating b(n), the minimum of b(P) over all n-point sets P with no three points collinear. We review results providing bounds on b(n) and mention some additional observations.     

Degree sets of degree uniform graphs

A graphG isn-degree uniform if for every nonnegative integerr, there are either no vertices of degreer orn vertices of degreer. For any integern≥2, a necessary and sufficient condition for a (finite, nonempty) set of positive integers to be the degree set of ann-degree uniform graph is given. Research supported in part by the South African Council for Scientific and Industrial Research     

On the number of minimal 1-Steiner trees

We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to ann-point set ind-dimensional space, by relating it to a family of convex decompositions of space. TheO(n ^d log^{2d 2}−d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor. The research of D. Eppstein was performed in part while visiting Xerox PARC.     

ON STABLE LINE SEGMENTS IN ALL TRIANGULATIONS OF A PLANAR POINT SET

Abstract. Let S be a set of finite plauar points. A llne segment L(p, q) with p, q E Sis called a stable line segment of S, if there is no Line segment with two endpoints in S intersecting L(p, q). In this paper, some geometric properties of the set of all stable line segments     

Extending analyticK-subanalytic functions

Letg:U→ℝ (U open in ℝⁿ) be an analytic and K-subanalytic (i. e. definable in ℝ _an ^K , whereK, the field of exponents, is any subfield ofℝ) function. Then the set of points, denoted Σ, whereg does not admit an analytic extension is K-subanalytic andg can be extended analytically to a neighbourhood of Ū\∑. Partially supported by the European RTN Network RAAG (contract no. HPRN-CT-00271)     

Isosceles Planar Subsets

A finite planar set is k -isosceles for k ≥ 3 if every k -point subset of the set contains a point equidistant from two others. There are three nonsimilar 3-isosceles sets with five points and one with six points. Eleven 4-isosceles sets with eight points are noted, and it is conjectured that no 4-isosceles set has nine points. Exactly one 4-isosceles 8-set has four points on a line, and every 4-isosceles set that includes the vertices of a square has fewer than eight points. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p391.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 1, 1997, and in revised form June 24, 1997.     

The existence of howell designs of siden+1 and order 2n

AHowell design of side s andorder 2n, or more briefly, anH(s, 2n), is ans×s array in which each cell either is empty or contains an unordered pair of elements from some 2n-set, sayX, such that (a) each row and each column is Latin (that is, every element ofX is in precisely one cell of each row and each column) and (b) every unordered pair of elements fromX is in at most one cell of the array. Atrivial Howell design is anH(s, 0) havingX=? and consisting of ans×s array of empty cells. A necessary condition onn ands for the existence of a nontrivialH(s, 2n) is that 0<n≦s≦2n-1. AnH(n+t, 2n) is said to contain a maximum trivial subdesign if somet×t subarray is theH(t, 0). This paper describes a recursive construction for Howell designs containing maximum trivial subdesigns and applies it to settle the existence question forH(n+1, 2n)’s: forn+1 a positive integer, there is anH(n+1, 2n) if and only ifn+1 ∉ {2, 3, 5}.     

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.     

The Coulomb energy of spherical designs on <Emphasis Type="Italic">S</Emphasis><Superscript>2</Superscript>

In this work we give upper bounds for the Coulomb energy of a sequence of well separated spherical n-designs, where a spherical n-design is a set of m points on the unit sphere S ² ⊂ ℝ³ that gives an equal weight cubature rule (or equal weight numerical integration rule) on S ² which is exact for spherical polynomials of degree ⩽ n. (A sequence Ξ of m-point spherical n-designs X on S ² is said to be well separated if there exists a constant λ > 0 such that for each m-point spherical n-design X ∈ Ξ the minimum spherical distance between points is bounded from below by .) In particular, if the sequence of well separated spherical designs is such that m and n are related by m = O(n ²), then the Coulomb energy of each m-point spherical n-design has an upper bound with the same first term and a second term of the same order as the bounds for the minimum energy of point sets on S ². Dedicated to Edward B. Saff on the occasion of his 60th birthday.     

A Lower Bound for Weak ɛ -Nets in High Dimension

   Abstract. A finite set N ⊂ R ^d is a weak ε-net for an n -point set X ⊂ R ^d (with respect to convex sets) if it intersects each convex set K with |K ∩ X| ≥ ε n . It is shown that there are point sets X ⊂ R ^d for which every weak ε -net has at least const ⋅

Arrangements of n Points whose Incident-Line-Numbers are at most n/2

We consider a set X of n noncollinear points in the Euclidean plane, and the set of lines spanned by X, where n is an integer with n ≥ 3. Let t(X) be the maximum number of lines incident with a point of X. We consider the problem of finding a set X of n noncollinear points in the Euclidean plane with t(X) ￡ ?n/2 ?{t(X) \le \lfloor n/2 \rfloor}, for every integer n ≥ 8. In this paper, we settle the problem for every integer n except n = 12k + 11 (k ≥ 4). The latter case remains open.     

Computing simple circuits from a set of line segments

We address the problem of connecting line segments to form the boundary of a simple polygon—a simple circuit. However, not every set of segments can be so connected. We present anO(n logn)-time algorithm to determine whether a set of segments, constrained so that each segment has at least one endpoint on the boundary of the convex hull of the segments, admits a simple circuit. Furthermore, this technique can also be used to compute a simple circuit of minimum perimeter, or a simple circuit that bounds the minimum area, with no increase in computational complexity.     

Multi-positive linear functionals on locally<Emphasis Type="Italic">C</Emphasis>*-algebras

We will show that ann×n matrix of continuous linear functionals on a locallyC*-algebraA, which satisfies the generalized positivity condition induces a continuous *-representation ofA on a Hilbert space. This generalizes the classical GNS-representation. Also, we give a necessary and sufficient condition such that this representation is irreducible, and determine a certain class of extreme points in the set of all continuous completely positive linear maps fromA toM _n (ℂ) that preserve identity.     

A completion problem for finite affine planes

A partial affine plane (PAP) of ordern is ann ²-setS of points together with a collection ofn-subsets ofS called lines such that any two lines meet in at most one point. We obtain conditions under which a PAP with nearlyn ²+n lines can be completed to an affine plane by adding lines. In particular, we make use of Bruck’s completion condition for nets to show that certain PAP’s with at leastn ²+n−√n can be completed and that forn≠3 any PAP withn ²+n−2 lines can be completed.