On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

Rigid sets in the plane

A compact set in the plane is rigid with respect to a norm if the norm isometries of the set act transitively on it. We show that if a norm has an infinite rigid set, then, up to linear transformation, the norm is Euclidean and the set is a circle. Our methods also yield a new characterisation of the ellipse.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.     

Properties of paradoxical sets in the plane

We show that every paradoxical subset of ² has empty interior, and every measurable paradoxical subset of ² has measure zero. We investigate how the proof fails in the hyperbolic plane, where there are paradoxical sets with interior points and with infinite measure.     

Instability of discrete point sets]{Instability of discrete point sets

Summary Let <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"3"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"4"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"5"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"6"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"7"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"8"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"9"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"10"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"11"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>X$ be a discrete subset of Euclidean $d$-space. We allow subsequently continuous movements of single elements, whenever the minimum distance to other elements does not decrease. We discuss the question, if it is possible to move all elements of $X$ in this way, for example after removing a finite subset $Y$ from $X$. Although it is not possible in general, we show the existence of such finite subsets $Y$ for many discrete sets $X$, including all lattices. We define the \textit{instability degree} of $X$ as the minimum cardinality of such a subset $Y$ and show that the maximum instability degree among lattices is attained by perfect lattices. Moreover, we discuss the $3$-dimensional case in detail.     

Classification of seven-point four-distance sets in the plane

A point set X in the plane is called a k-distance set if there are exactly k different distances between two distinct points in X. In this paper, we classify 7-point 4-distance sets and show that there are forty two 7-point 4-distance sets in the plane up to isomorphism, we also give some results about diameter graphs.     

Properties of connected ortho-convex sets in the plane

Topological properties of connected ortho-convex sets in the plane, i.e., connected sets convex along the horizontal and vertical lines are studied. Several geometric statements concerning the ortho-separation of ortho-convex sets are proved.     

More onk-sets of finite sets in the plane

For a setS ofn points in the plane and forK {1, 2, ..., [1/2n]}, letf _K (S) denote the number of subsets ofS with cardinalityk K which can be cut offS by a straight line. We show that there is a positive constantc such thatf _K (S)<cn ( _{k K} k)^1/2.This research was carried out during the author's stay at the University of Leiden, The Netherlands.     

Low-discrepancy point sets

Various point sets in thes-dimensional unit cube with small discrepancy are constructed.Dedicated to Professor E. Hlawka on the occasion of his seventieth birthday     

On the discrepancy of convex plane sets

LetD ₂ (N) be the discrepancy function of the class of convex sets in the unit square [0, 1)² as defined in the introduction. A well known result of W. M. Schmidt states thatD ₂ f(N)>constN ^1/3. In this paper it is shown that Schmidt's bound is nearly best possible, more precisely, $$D_2 (N)< const N^{1/3} (\log N)^4 .$$      

General decomposition theorems form-convex sets in the plane

A setS inR ^dis said to bem-convex,m≧2, if and only if for everym distinct points inS, at least one of the line segments determined by these points lies inS. Clearly any union ofm?1 convex sets ism-convex, yet the converse is false and has inspired some interesting mathematical questions: Under what conditions will anm-convex set be decomposable intom?1 convex sets? And for everym≧2, does there exist aσ(m) such that everym-convex set is a union ofσ(m) convex sets? Pathological examples convince the reader to restrict his attention to closed sets of dimension≦3, and this paper provides answers to the questions above for closed subsets of the plane. IfS is a closedm-convex set in the plane,m ≧ 2, the first question may be answered in one way by the following result: If there is some lineH supportingS at a pointp in the kernel ofS, thenS is a union ofm ? 1 convex sets. Using this result, it is possible to prove several decomposition theorems forS under varying conditions. Finally, an answer to the second question is given: Ifm≧3, thenS is a union of (m?1)³2 ^m?3 or fewer convex sets.     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

Empty pseudo-triangles in point sets

We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n²) and Θ(n³) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n³) and Θ(n⁶). If we count only star-shaped pseudo-triangles, the bounds are Θ(n²) and Θ(n⁵). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n³) time. In the general case, the running times are O(n⁶) for the maximization problems and O(nlogn) for the minimization problems.     

Reconstructing plane sets from projections

We give some uniqueness results for the problem of determining a finite set in the plane knowing its projections alongm directions. We apply the results to the problem of the reconstruction of a homogeneous convex body with a finite set of spherical disjoint holes. Ifm X-ray pictures with directions in some plane are given, then the problem is well posed provided the number of the holes is less than or equal tom and the set of the directions satisfies a suitable condition.     

Distances realized by sets covering the plane

A proof is given of the (known) result that, if real n-dimensional Euclidean space Rⁿ is covered by any n + 1 sets, then at least one of these sets is such that each distance d(0 < d < ∞) is realized as the distance between two points of the set. In particular, this result holds if the plane is covered by three sets; but it does not necessarily hold if the plane is covered by six sets. If each set in a covering of the plane fails to realize the same distance d, say d = 1, and if the sets are either closed or simultaneously divisible into region (in a sense to be made precise), then at least six sets are needed and seven suffice, and the number of closed sets needed is at least as great as the number simultaneously divisible into regions.