A family of examples showing that no Krasnosel’skii number exists for orthogonal polygons starshaped via staircase n-paths

Let S be a simply connected orthogonal polygon in the plane. A family of examples will establish the following result. For every n ≥ 2, there exists no Krasnosel’skii number h(n) which satisfies this property: If every h(n) points of S are visible via staircase n-paths from a common point, then S is starshaped via staircase n-paths.     

On the dimension of ordered sets with the 2-cutset property

An ordered setP is said to have 2-cutset property if, for every elementx ofP, there is a setS of elements ofP which are noncomparable tox, with |S|?2, such that every maximal chain inP meets {x}∪S. We consider the following question: Does there exist ordered sets with the 2-cutset property which have arbitrarily large dimension? We answer the question in the negative by establishing the following two results.Theorem: There are positive integersc andd such that every ordered setP with the 2-cutset property can be represented asP=X∪Y, whereX is an ordinal sum of intervals ofP having dimension ?d, andY is a subset ofP having width ?c. Corollary: There is a positive integern such that every ordered set with the 2-cutset property has dimension ?n.     

Cells in any simple polygon formed by a planar point set

Let P be a finite point set in general position in the plane. We consider empty convex subsets of P such that the union of the subsets constitute a simple polygon S whose dual graph is a path, and every point in P is on the boundary of S. Denote the minimum number of the subsets in the simple polygons S's formed by P by f_p(P), and define the maximum value of f_p(P) by F_p(n) over all P with n points. We show that ⌈(4n-17)/15⌉?F_p(n)?⌊n/2⌋.     

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

A Krasnosel’skii theorem for orthogonal polygons starshaped via staircase (n + 1)-paths

Let S be a simply connected orthogonal polygon in the plane, and let n be fixed, n ≥ 1. If every two points of S are visible via staircase n-paths from a common point of S, then S is starshaped via staircase (n + 1)-paths. Moreover, the associated staircase (n + 1)-kernel is staircase (n + 1)-convex. The number two is best possible, and the number n + 1 is best possible for n ≥ 2.     

On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

The smallest graphs with certain adjacency properties

A graph is said to have property P₁,_n if for every sequence of n + 1 points, there is another point adjacent only to the first point. It has previously been shown that almost all graphs have property P₁,_n. It is easy to verify that for each n, there is a cube with this property. A more delicate question asks for the construction of the smallest graphs having property P₁,_n. We find that this problem is intimately related with the discovery of the highly symmetric graphs known as cages, and are thereby enabled to resolve this question for 1?n?6.     

The number of lines determined by a polygon

Given a polygon P in the Euclidean plane, what can be said about the number of lines in the plane which contain at least one edge of P? If P has n edges, it is easy to see that at most n lines contain an edge of P. Further, any convex polygon with n edges provides an example of such a situation. The question of interest here is what is the smallest number of lines, each containing one or more edges, which may be determined by a polygon with n edges? This number is not n and in fact does not even grow like some constant, of necessity less than one, times n. Rather, it grows like √2n. We are actually able to determine this minimum exactly for most values of n and to within one for all values of n.     

Multiple closed geodesics on bumpy Finsler n-spheres

In this paper we prove that for every bumpy Finsler metric F on every rationally homological n-dimensional sphere Sn with n?2, there exist always at least two distinct prime closed geodesics.     

Cut points in some connected topological spaces

We prove that a connected topological space with endpoints has exactly two non-cut points and every cut point is a strong cut point; it follows that such a space is a COTS and the only two non-cut points turn out to be endpoints (in each of the two orders) of the COTS. A non-indiscrete connected topological space with exactly two non-cut points and having only finitely many closed points is proved homeomorphic to a finite subspace of the Khalimsky line. Further, it is shown, without assuming any separation axiom, that in a connected and locally connected topological space X, for a, b in X, S[a,b] is compact whenever it is closed. Using this result we show that an H(i) connected and locally connected topological space with exactly two non-cut points is a compact COTS with end points.     

Metric Möbius geometry and a characterization of spheres

We obtain a Möbius characterization of the n-dimensional spheres S ⁿ endowed with the chordal metric d ₀. We show that every compact extended Ptolemy metric space with the property that every three points are contained in a circle is Möbius equivalent to (S ⁿ , d ₀) for some n ≥ 1.     

Absolute Points of Continuous and Smooth Polarities

This paper deals with sets of absolute points of continuous or smooth polarities in compact, connected or smooth projective planes, called topological polar unitals or smooth polar unitals, respectively. We will show that topological polar unitals are Z₂-homology spheres. In the four-dimensional case, a topological polar unital U is either a topological oval, or any line which intersects U in more than one point intersects in a set homeomorphic to S₁. Smooth polar unitals turn out to be smoothly embedded submanifolds of the point space. Moreover, secants intersect such unitals transversally. For these unitals, we will obtain full information on the existence of secants, tangents and exterior lines through given points according to their position with respect to the unital. The main result of this paper states that the possible dimensions of smooth polar unitals coincide with those of sets of absolute points of continuous polarities in the classical projective planes P₂F, F?{R,C,H,O}. Finally, we will prove that smooth polar unitals in four-dimensional smooth projective planes are topological ovals or are homeomorphic to S₃.     

Characterizations of n-connected and n-line connected graphs

The following two theorems are proved: (1) A graph G with at least n + 1 points, n ≥ 2, is n-connected if and only if for each set S of n distinct points of G and for each two point subset T of S there is a cycle of G that contains the points of T and avoids the points of S ? T. (2) A graph G with at least n + 1 lines, n ≥ 2, with no isolated points is n-line connected if and only if for each set S of n distinct lines of G and for each two line subset T of S there is a circuit of G that contains the lines of T and avoids the lines of S ? T.     

On polyhedra induced by point sets in space

Given a set S of n?3 points in the plane (not all on a line) it is well known that it is always possible to polygonize S, i.e., construct a simple polygon P such that the vertices of P are precisely the given points in S. For example, the shortest circuit through S is a simple polygon. In 1994, Grünbaum showed that an analogous theorem holds in R³. More precisely, if S is a set of n?4 points in R³ (not all of which are coplanar) then it is always possible to polyhedronize S, i.e., construct a simple (sphere-like) polyhedron P such that the vertices of P are precisely the given points in S. Grünbaum's constructive proof may yield Schönhardt polyhedra that cannot be triangulated. In this paper several alternative algorithms are proposed for constructing such polyhedra induced by a set of points, which may always be triangulated, and which enjoy several other useful properties as well. Such properties include polyhedra that are star-shaped, have Hamiltonian skeletons, and admit efficient point-location queries. We show that polyhedronizations with a variety of such useful properties can be computed efficiently in O(nlogn) time. Furthermore, we show that a tetrahedralized, xy-monotonic, polyhedronization of S may be computed in time O(n^1+ε), for any ε>0.     

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.     

Factoring compact operators

We consider the following problem: Does there exist a separable Banach spaceZ such that every compact operator can be factored as a productTS withT, S compact, rangeS=DomainT=Z? Our investigation yields a reasonable partial solution to this problem as well as the following independent result: A Banach space which has theλ-metric approximation property can be embedded as a complemented subspace of aπ _λ space.     

Multiple-guard kernels of simple polygons

We study a generalization of the kernel of a polygon. A polygonP isk guardable if there arek points inP such that, for all pointsp inP, there is at least one of thek points that seesp. We call thek points ak-guard set ofP and thek-kernel of a polygonP is the union of allk-guard sets ofP. The usual definition of the kernel of a polygon is now the one-kernel in this notation.We show that the two-kernel of a simple polygonP withn edges has O(n⁴) components and that there are polygons whose two-kernel has (n) components. Moreover, we show that the components of the two-kernel of a simple polygon can be paired in a natural manner which implies that the two-kernel of a simple polygon has either one component or an even number of components. Finally, we consider the question of whether there is a non-star-shaped simple polygonP such that 2-kernel(P) = P. We show that when the two-kernel has only one component, it contains a hole; hence, the two-kernel of a simple polygonP is neverP itself. For everyk 1, there are, however, polygonsP _k with holes such thatk-kernel(P_k) = P_k.This work was supported under grant No. Ot 64/8-1, Diskrete Probleme from the the Deutsche Forschungsgemeinschaft, grants from the Natural Sciences and Engineering Council of Canada, from the Information Technology Research Centre of Ontario, and from the Research Grants Council of Hong Kong.     

Coherent orientations and series-parallel networks

Let p be an edge of the graph G. An orientation of G is p-coherent if the set of directed circuits is exactly the set of circuits containing the edge p. Theorem: A matroidally connected graph G is a series-parallel network if and only if for every edge p of G, there exists a p-coherent orientation.     

Spanning Star Trees in Regular Graphs

For a subset W of vertices of an undirected graph G, let S(W) be the subgraph consisting of W, all edges incident to at least one vertex in W, and all vertices adjacent to at least one vertex in W. If S(W) is a tree containing all the vertices of G, then we call it a spanning star tree of G. In this case W forms a weakly connected but strongly acyclic dominating set for G. We prove that for every r ≥ 3, there exist r-regular n-vertex graphs that have spanning star trees, and there exist r-regular n-vertex graphs that do not have spanning star trees, for all n sufficiently large (in terms of r). Furthermore, the problem of determining whether a given regular graph has a spanning star tree is NP-complete.