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.     

Congruence Criteria for Finite Subsets of Quaternionic Elliptic and Quaternionic Hyperbolic Spaces

We investigate congruence classes of m-tuples of points in the quaternionic elliptic space ?P ⁿ . We establish a canonical bijection between the set of congruence classes of m-tuples of points in ?P ⁿ and the set of equivalence classes of positive semidefinite Hermitian m×m matrices of rank at most n+1 with the 1's on the diagonal. We show that with each m-tuple of points in ?P ⁿ is associated a tuple of points on the real unit sphere S ². Then we get that the congruence class of an m-tuple of points in ?P ⁿ is determined by the congruence classes of all its triangles and by the direct congruence class of the associated tuple on the sphere S ² provided that no pair of points of the m-tuple has distance π/2. Finally we carry out the same kind of investigation for the quaternionic hyperbolic space ?H ⁿ . Most of the results are completely analogous, although there are also some interesting differences.     

Separators of points on algebraic surfaces

For a finite set of points X⊆Pⁿ and for a given point P∈X, the notion of a separator of P in X (a hypersurface containing all the points in X except P) and of the degree of P in X, (the minimum degree of these separators) has been largely studied. In this paper we extend these notions to a set of points X on a projectively normal surface S⊆Pⁿ, considering as separators arithmetically Cohen-Macaulay curves and generalizing the case S=P² in a natural way. We denote the minimum degree of such curves as and we study its relation to . We prove that if S is a variety of minimal degree these two terms are explicitly related by a formula, whereas only an inequality holds for other kinds of surfaces.     

Planar zero divisor graphs of partially ordered sets

We associate a graph G ^?(P) to a partially ordered set (poset, briefly) with the least element?0, as an undirected graph with vertex set P ^?=P?{0} and, for two distinct vertices x and y, x is adjacent to?y in?G ^?(P) if and only if {x,y} ^? ={0}, where, for a subset?S of?P, S ^? is the set of all elements x∈P with x≦s for all s∈S. We study some basic properties of?G ^?(P). Also, we completely investigate the planarity of?G ^?(P).     

Patroids

A matroid M over a set E of elements is semiseparated by a partition {S¹, S²} of E iff rank E = rank S¹ + rank S² + 1. Such a semiseparation defines in each Sⁱ a pair of matroids or patroid Pⁱ = (Mⁱ, mⁱ); the two patroids P¹, P² weld to form M. The operations of removing and contracting a non-degenerate element of a matroid produce a patroid. The properties of patroids, their bases, and circuits are discussed.     

On degrees in random triangulations of point sets

We study the expected number of interior vertices of degree i in a triangulation of a planar point set S, drawn uniformly at random from the set of all triangulations of S, and derive various bounds and inequalities for these expected values. One of our main results is: For any set S of N points in general position, and for any fixed i, the expected number of vertices of degree i in a random triangulation is at least γiN, for some fixed positive constant γi (assuming that N>i and that at least some fixed fraction of the points are interior).We also present a new application for these expected values, using upper bounds on the expected number of interior vertices of degree 3 to get a new lower bound, Ω(N^2.4317), for the minimal number of triangulations any N-element planar point set in general position must have. This improves the previously best known lower bound of Ω(N^2.33).     

n-bathycenters

Does there exist a polygon with the property that for a suitable point p in the plane every ray with endpoint p intersects the polygon in exactly n connected components? Does there exist a polygon with the property that there are two such points, or three, or a segment of such points? For polygon P call a point p with the property that every ray from p intersects P in exactly n connected components n-isobathic with respect to P. Define the n-bathycenter of a polygon P as the set of all points p that are n-isobathic with respect to P. Further define a set S to be an n-bathycenter if there exists a polygon P of which S is the n-bathycenter. This paper deals with the characterization of 2- and 3-bathycenters, together with some results on the general case.     

Stable Stationary Harmonic Maps to Spheres

For k ≥ 3, we establish new estimate on Hausdorff dimensions of the singular set of stable-stationary harmonic maps to the sphere S^k. We show that the singular set of stable-stationary harmonic maps from B5 to 83 is the union of finitely many isolated singular points and finitely many HSlder continuous curves. We also discuss the minimization problem among continuous maps from B^n to S^2.     

A nondensity property of preperiodic points on Chebyshev dynamical systems

Let k be a number field with algebraic closure , and let S be a finite set of primes of k, containing all the infinite ones. Consider a Chebyshev dynamical system on P². Fix the effective divisor D of P² that is equal to a line nondegenerate on²[−2,2]. Then we will prove that the set of preperiodic points on which are S-integral relative to D is not Zariski dense in P².     

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.     

Facility location problems in the plane based on reverse nearest neighbor queries

For a finite set of points S, the (monochromatic) reverse nearest neighbor (RNN) rule associates with any query point q the subset of points in S that have q as its nearest neighbor. In the bichromatic reverse nearest neighbor (BRNN) rule, sets of red and blue points are given and any blue query is associated with the subset of red points that have it as its nearest blue neighbor. In this paper we introduce and study new optimization problems in the plane based on the bichromatic reverse nearest neighbor (BRNN) rule. We provide efficient algorithms to compute a new blue point under criteria such as: (1) the number of associated red points is maximum (MAXCOV criterion); (2) the maximum distance to the associated red points is minimum (MINMAX criterion); (3) the minimum distance to the associated red points is maximum (MAXMIN criterion). These problems arise in the competitive location area where competing facilities are established. Our solutions use techniques from computational geometry, such as the concept of depth of an arrangement of disks or upper envelope of surface patches in three dimensions.     

On illumination in the plane by line segments

We show that S E ² contains a line segment illuminator if any two points of S are illuminated by a line segment of S in a given direction or if any eight points of S are illuminated by a connected set of line segments of S and a certain connectedness condition is fulfilled. We also show that if any three points of S E ² are illuminated by a translate in S of a line segment T, then S contains a line segment illuminator, which is also a translate of T. As a further result, we have that if any three points of a polygon P are illuminated by some line segment of P then the so-called link center of P illuminates P. Finally, we prove that if any three points of an o-symmetric polygon P are illuminated by a line segment of P through the point o then P contains an o-symmetric convex illuminator which is either a line segment or a parallelogram.Partially supported by the Hungarian National Foundation for Scientific Research grant number 1238.Partially supported by the Natural Sciences and Engineering Research Council of Canada.     

On affine groups admitting invariant two-point sets

A two-point set is a subset of the plane which meets every line in exactly two points. We discuss previous work on the topological symmetries of a two-point set, and show that there exist subgroups of S¹ which do not leave any two-point set invariant. Further, we show that two-point sets may be chosen to be topological groups, in which case they are also homogeneous.     

On the maximum empty rectangle problem

Given a rectangle A and a set S of n points in A, we consider the problem, called the maximum empty rectangle problem, of finding a maximum area rectangle that is fully contained in A and does not contain any point of S in its interior. An O(n²) time algorithm is presented. Furthermore, it is shown that if the points of S are drawn randomly and independently from A, the problem can be solved in O(n(log n)²) expected time.     

A better decomposition theorem for simply connected m-convex sets

A set S in R^d is said to be m-convex, m ? 2, if and only if for every m points in S, at least one of the line segments determined by these points lies in S. For S a closed m-convex set in R², various decomposition theorems have been obtained to express S as a finite union of convex sets. However, the previous bounds may be lowered further, and we have the following result:In case S is simply connected, then S is a union of σ(m) or fewer convex sets, where $\text{σ(m) = [(m ?}\text{N}\text{)(m ?}\text{3}\text{2}\text{) +}\text{3}\text{2}\text{]}$.Moreover, this result induces an improved decomposition in the general case as well.     

AnR danalogue of Valentine’s theorem on 3-convex sets

This paper deals with anR ^danalogue of a theorem of Valentine which states that a closed 3-convex setS in the plane is decomposable into 3 or fewer closed convex sets. In Valentine’s proof, the points of local nonconvexity ofS are treated as vertices of a polygonP contained in the kernel ofS, yielding a decomposition ofS into 2 or 3 convex sets, depending on whetherP has an even or odd number of edges. Thus the decomposition actually depends onc(P′), the chromatic number of the polytopeP′ dual toP. A natural analogue of this result is the following theorem: LetS be a closed subset ofR ^d, and letQ denote the set of points of local nonconvexity ofS. We require thatQ be contained in the kernel ofS and thatQ coincide with the set of points in the union of all the (d − 2)-dimensional faces of somed-dimensional polytopeP. ThenS is decomposable intoc(P′) closed convex sets.     

Laudal-type theorems in P

In this paper we classify all integral, non-degenerate, locally Cohen-Macaulay subvarieties in P^N, whose general complementary section is a complete intersection set of points: they are either complete intersections or curves on a quadric surface in P³ or degree 4 arithmetically Buchsbaum surfaces in P⁴ (i.e. the Veronese surface or a degeneration of it). As a consequence we show that every locally Cohen-Macaulay threefold in P^S of degree 4 is a complete intersection.Moreover, we obtain a generalization of Laudal's Lemma to threefolds in P⁵ and fourfolds in P⁶, which gives a bound on the degree of a codimension 2, integral subvariety X in P^N, depending both on N and a non-lifting level s of X.     

From the Icosahedron to Natural Triangulations of??P 2 and S 2��S 2

We present two constructions in this paper: (a) a 10-vertex triangulation $\mathbb{C}P^{2}_{10}$ of the complex projective plane ?P ² as a subcomplex of the join of the standard sphere ( $S^{2}_{4}$ ) and the standard real projective plane ( $\mathbb{R}P^{2}_{6}$ , the decahedron), its automorphism group is A ₄; (b) a 12-vertex triangulation (S ²×S ²)₁₂ of S ²×S ² with automorphism group 2S ₅, the Schur double cover of the symmetric group S ₅. It is obtained by generalized bistellar moves from a simplicial subdivision of the standard cell structure of S ²×S ². Both constructions have surprising and intimate relationships with the icosahedron. It is well known that ?P ² has S ²×S ² as a two-fold branched cover; we construct the triangulation $\mathbb{C}P^{2}_{10}$ of ?P ² by presenting a simplicial realization of this covering map S ²×S ²???P ². The domain of this simplicial map is a simplicial subdivision of the standard cell structure of S ²×S ², different from the triangulation alluded to in (b). This gives a new proof that Kühnel??s $\mathbb{C}P^{2}_{9}$ triangulates ?P ². It is also shown that $\mathbb{C}P^{2}_{10}$ and (S ²×S ²)₁₂ induce the standard piecewise linear structure on ?P ² and S ²×S ² respectively.