Total curvatures of model surfaces control topology of complete open manifolds with radial curvature bounded below: I

We investigate the finiteness structure of a complete non-compact n-dimensional Riemannian manifold M whose radial curvature at a base point of M is bounded from below by that of a non-compact von Mangoldt surface of revolution with its total curvature greater than π. We show, as our main theorem, that all Busemann functions on M are exhaustions, and that there exists a compact subset of M such that the compact set contains all critical points for any Busemann function on M. As corollaries by the main theorem, M has finite topological type, and the isometry group of M is compact.     

Two point sets with additional properties

A subset of the plane is called a two point set if it intersects any line in exactly two points. We give constructions of two point sets possessing some additional properties. Among these properties we consider: being a Hamel base, belonging to some σ-ideal, being (completely) nonmeasurable with respect to different σ-ideals, being a κ-covering. We also give examples of properties that are not satisfied by any two point set: being Luzin, Sierpiński and Bernstein set. We also consider natural generalizations of two point sets, namely: partial two point sets and n point sets for n = 3, 4, …, ?₀, ?₁. We obtain consistent results connecting partial two point sets and some combinatorial properties (e.g. being an m.a.d. family).     

Polygonizations of point sets in the plane

We examine the different ways a set ofn points in the plane can be connected to form a simple polygon. Such a connection is called apolygonization of the points. For some point sets the number of polygonizations is exponential in the number of points. For this reason we restrict our attention to star-shaped polygons whose kernels have nonempty interiors; these are callednondegenerate star-shaped polygons.We develop an algorithm and data structure for determining the nondegenerate star-shaped polygonizations of a set ofn points in the plane. We do this by first constructing an arrangement of line segments from the point set. The regions in the arrangement correspond to the kernels of the nondegenerate star-shaped polygons whose vertices are the originaln points. To obtain the data structure representing this arrangement, we show how to modify data structures for arrangements of lines in the plane. This data structure can be computed inO(n ⁴) time and space. By visiting the regions in this data structure in a carefully chosen order, we can compute the polygon associated with each region inO(n) time, yielding a total computation time ofO(n ⁵) to compute a complete list ofO(n ⁴) nondegenerate star-shaped polygonizations of the set ofn points.     

Sets of type (m,n) in the affine and projective planes of order nine

In this paper we give the results of exhaustive computer searches for sets of points of type (m, n) in the projective and affine planes of order nine. In particular, as the list of planes of order nine is known to be complete, our results are also complete. We also examine all known constructions of sets of type (m, n) that apply to the planes of order nine, in an attempt to summarise and extend all existing knowledge about such sets. The contrast between known constructions and our computer results leads us to conclude that sets of type (m, n) are far more numerous than was previously thought.     

Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G _n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD _n−1 of order n−1 with the path P _n ⁽²⁾ on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P(G _n )=P(P _n ⁽²⁾)[P(QAD _n−1)]². On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid—i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds. We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases—graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls. We apply the above results to enumerate all the symmetry classes of spanning trees of the even Aztec diamonds, and all the symmetry classes not involving rotations of the spanning trees of odd and mixed Aztec diamonds. We also enumerate all but the base case of the symmetry classes of perfect matchings of odd square grids with the central vertex removed. In addition, we obtain a product formula for the number of spanning trees of Aztec pillowcases. Research supported in part by NSF grant DMS-0500616.     

Neighborly combinatorial 3-manifolds with dihedral automorphism group

It is well known that for anyn≧5 the boundary complex of the cyclic 4-polytopeC(n, 4) is a neighborly combinatorial 3-sphere admitting a vertex transitive action of the dihedral groupD _n of order 2n. In this paper we present a similar series of neighborly combinatorial 3-manifolds withn≧9 vertices, each homeomorphic to the “3-dimensional Klein bottle”. Forn=9 andn=10 these examples have been observed. before by A. Altshuler and L. Steinberg. Moreover we give a computer-aided enumeration of all neighborly combinatorial 3-manifolds with such a symmetry and with at most 19 vertices. It turns out that there are only four other types, one with 10, 15, 17, 19 vertices. We also discuss the more general case of manifolds with cyclic automorphism groupC _n.     

Witness Rectangle Graphs

In a witness rectangle graph (WRG) on vertex point set P with respect to witness point set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally, we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n points.     

Computable choice functions for computable linear orderings

A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. We obtain a partial characterization of the computable linear order‐types for which each computable model has a computable choice set, and a full characterization in the relativized case; Every model of the linear order‐type α of degree ≤ d has a choice set of degree ≤ d iff α can written as a finite sum of order‐types, each of which either has finitely many blocks, or has order‐type n · η for some integer n.     

Visibility with One Reflection

We extend the concept of the polygon visible from a source point S in a simple polygon by considering visibility with two types of reflection, specular and diffuse. In specular reflection a light ray reflects from an edge of the polygon according to the rule: the angle of incidence equals the angle of reflection. In diffuse reflection a light ray reflects from an edge of the polygon in all inward directions. Several geometric and combinatorial properties of visibility polygons under these two types of reflection are described, when at most one reflection is permitted. We show that the visibility polygon Vs(S) under specular reflection may be nonsimple, while the visibility polygon Vd(S) under diffuse reflection is always simple. We present a Θ(n ² ) worst-case bound on the combinatorial complexity of both Vs(S) and Vd(S) and describe simple O(n ² log ² n) time algorithms for constructing the sets. Received September 27, 1995, and in revised form October 24, 1997.     

On the complexity of a single cell in certain arrangements of surfaces related to motion planning

We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n ²) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement in each case that we study can be Θ(n ³) in the worst case, and our single-cell bounds are of the formO(n ² α(n)), O(n ² logn), orO(n ² α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space, where the bounds are Θ(n) and Θ(n ²), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell. A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323.     

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

Planar and affine spaces

In this note, we characterize finite three-dimensional affine spaces as the only linear spaces endowed with set Ω of proper subspaces having the properties (1) every line contains a constant number of points, say n, with n>2; (2) every triple of noncollinear points is contained in a unique member of Ω; (3) disjoint or coincide is an equivalence relation in Ω with the additional property that every equivalence class covers all points. We also take a look at the case n=2 (in which case we have a complete graph endowed with a set Ω of proper complete subgraphs) and classify these objects: besides the affine 3-space of order 2, two small additional examples turn up. Furthermore, we generalize our result in the case of dimension greater than three to obtain a characterization of all finite affine spaces of dimension at least 3 with lines of size at least 3.     

Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns

In this work, we study the kth local base, which is a generalization of the base, of a primitive non-powerful nearly reducible sign pattern of order n ≥ 7. We obtain the sharp bound together with a complete characterization of the equality case, of the kth local bases for primitive non-powerful nearly reducible sign patterns. We also show that there exist “gaps” in the kth local base set of primitive non-powerful nearly reducible sign patterns.     

Equivelar maps on the torus

We give a classification of all equivelar polyhedral maps on the torus. In particular, we classify all triangulations and quadrangulations of the torus admitting a vertex transitive automorphism group. These are precisely the ones which are quotients of the regular tessellations {3,6}, {6,3} or {4,4} by a pure translation group. An explicit formula for the number of combinatorial types of equivelar maps (polyhedral and non-polyhedral) with n vertices is obtained in terms of arithmetic functions in elementary number theory, such as the number of integer divisors of n. The asymptotic behaviour for n→∞ is also discussed, and an example is given for n such that the number of distinct equivelar triangulations of the torus with n vertices is larger than n itself. The numbers of regular and chiral maps are determined separately, as well as the ones for all other kinds of symmetry. Furthermore, arithmetic properties of the integers of type p²+pq+q² (or p²+q², resp.) can be interpreted and visualized by the hierarchy of covering maps between regular and chiral equivelar maps or type {3,6} (or {4,4}, resp.).     

Nonfacets for shellable spheres

We generalize the notion of a map on a 2-sphere to maps on then-sphere and then show that there exist combinatorial types of countries that cannot be the only type of country for a shellablen-sphere. This generalizes the well known theorem that there are no maps on the 2-sphere all of whose countries arek-gons for anyk≧6. Research supported by N.S.F. grant, number GP-42941     

Maintaining the Extent of a Moving Point Set

Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of S . If the points in S move with algebraic motions, these structures process O(n ^2+\eps ) events. We also give constructions showing that Ω(n ² ) combinatorial changes are possible for these extent functions even if each point is moving with constant velocity. We give a similar construction and upper bound for the convex hull, improving known results. Received April 25, 2000, and in revised form September 25, 2000. Online publication May 4, 2001.