A geometric realization without self-intersections does exist for Dyck's regular map

Even in our decade there is still an extensive search for analogues of the Platonic solids. In a recent paper Schulte and Wills [13] discussed properties of Dyck's regular map of genus 3 and gave polyhedral realizations for it allowing self-intersections. This paper disproves their conjecture in showing that there is a geometric polyhedral realization (without self-intersections) of Dyck's regular map {3, 8}₆ already in Euclidean 3-space. We describe the shape of this new regular polyhedron.     

How to Exhibit Toroidal Maps in Space

Steinitz's theorem states that a graph is the 1-skeleton of a convex polyhedron if and only if it is 3-connected and planar. The polyhedron is called a geometric realization of the embedded graph. Its faces are bounded by convex polygons whose points are coplanar. A map on the torus does not necessarily have such a geometric realization. In this paper we relax the condition that faces are the convex hull of coplanar points. We require instead that the convex hull of the points on a face can be projected onto a plane so that the boundary of the convex hull of the projected points is the image of the boundary of the face. We also require that the interiors of the convex hulls of different faces do not intersect. Call this an exhibition of the map. A map is polyhedral if the intersection of any two closed faces is simply connected. Our main result is that every polyhedral toroidal map can be exhibited. As a corollary, every toroidal triangulation has a geometric realization.     

On the structure of complete simply connected embedded minimal surfaces

The helicoid and the plane are the only known complete simply connected minimal surfaces without self-intersections. In this paper we make an analytic study of this class of surfaces by first deforming them continuously into surfaces with self-intersections. Next, we study the (backward) time evolution of the set of self-intersections and see what geometric conditions must prevail in order for the self-intersections to rush off to infinity in finite time. As a result of this program it is shown that any surface of the type considered above has to satisfy at least one of five geometric possibilities. The first two of these alternatives are pathological, the third one is satisfied by the plane, and the next two are satisfied by the helicoid.     

Geometric realizations for Dyck's regular map on a surface of genus 3

Klein's and Dyck's regular maps on Riemann surfaces of genus 3 were one impetus for the theory of regular maps, automorphic functions, and algebraic curves. Recently a polyhedral realization inE ³ of Klein's map was discovered [18], thereby underlining the strong analogy to the icosahedron. In this paper we show that Dyck's map can be realized inE ³ as a polyhedron of Kepler-Poinsot-type, i.e., with maximal symmetry and minimal self-intersections. Furthermore some closely related polyhedra and a Kepler-Poinsot-type realization of Sherk's regular map of genus 5 are discussed.     

Decompositions and boundary coverings of non-convex fat polyhedra

We show that any locally-fat (or (α,β)-covered) polyhedron with convex fat faces can be decomposed into O(n) tetrahedra, where n is the number of vertices of the polyhedron. We also show that the restriction that the faces are fat is necessary: there are locally-fat polyhedra with non-fat faces that require Ω(n²) pieces in any convex decomposition. Furthermore, we show that if we want the tetrahedra in the decomposition to be fat themselves, then their number cannot be bounded as a function of n in the worst case. Finally, we obtain several results on the problem where we want to only cover the boundary of the polyhedron, and not its entire interior.     

Isogonal Prismatoids

The study of the polyhedra (in Euclidean 3-space) in which faces may be self-intersecting polygons, and distinct faces may intersect in various ways, was quite fashionable about a century ago. The Kepler—Poinsot regular polyhedra, and several of their generalizations, were investigated about that time by Cayley, Wiener, Badoureau, Fedorov, Hess, Pitsch, and others; the accumulated wisdom was presented in Max Brückner's well-known book Vielecke und Vielflache in 1900. Despite the intrinsic interest of the topic, and its relations to various other disciplines, there have been very few additional investigations during the intervening century, except for discussions of uniform polyhedra. In particular, there has been no mention or clarification of the many errors and other shortcomings of Brückner's book. One of our aims is to point out the extent of these inadequacies; they are illustrated by a discussion of isogonal prismatoids, the investigation of which is our main objective. A prismatoid is a polyhedron having all its vertices in two parallel planes. Familiar examples are prisms and antiprisms. A polyhedron P is isogonal if all its vertices form one transitivity class under isometric symmetries of P. Although these restrictions appear very severe, there exist many different kinds of isogonal prismatoids. Some general concepts concerning polyhedra with possible self-intersections are presented, and several classes of isogonal prismatoids are discussed in some detail. Received April 5, 1995.     

Klein polyhedra and relative minima of lattices

We prove that in ?³, the relative minima of almost any lattice belong to the surface of the corresponding Klein polyhedron. We also prove, for almost any lattice in ?³, that the set of relative minima with nonnegative coordinates coincides with the union of the set of extremal points of the Klein polyhedron and a set of special points belonging to the triangular faces of the Klein polyhedron.     

On the Quasiconcave Bilevel Programming Problem

Bilevel programming involves two optimization problems where the constraint region of the first-level problem is implicitly determined by another optimization problem. In this paper, we consider the case in which both objective functions are quasiconcave and the constraint region common to both levels is a polyhedron. First, it is proved that this problem is equivalent to minimizing a quasiconcave function over a feasible region comprised of connected faces of the polyhedron. Consequently, there is an extreme point of the polyhedron that solves the problem. Finally, it is shown that this model includes the most important case where the objective functions are ratios of concave and convex functions     

Isohedra with nonconvex faces

An isohedron is a 3-dimensional polyhedron all faces of which are equivalent under symmetries of the polyhedron. Many well known polyhedra are isohedra; among them are the Platonic solids, the polars of Archimedean polyhedra, and a variety of polyhedra important in crystallography. Less well known are isohedra with nonconvex faces. We establish that such polyhedra must be starshaped and hence of genus 0, that their faces must be star-shaped pentagons with one concave vertex, and that they are combinatorially equivalent to either the pentagonal dodecahedron, or to the polar of the snub cube or snub dodecahedron.Supported in part by grants from the USA National Science Foundation.     

A new bound on the local density of sphere packings

It is shown that a packing of unit spheres in three-dimensional Euclidean space can have density at most 0.773055..., and that a Voronoi polyhedron defined by such a packing must have volume at least 5.41848... These bounds are superior to the best bounds previously published [5] (0.77836 and 5.382, respectively), but are inferior to the tight bounds of 0.7404... and 5.550... claimed by Hsiang [2]. Our bounds are proved by cutting a Voronoi polyhedron into cones, one for each of its faces. A lower bound is established on the volume of each cone as a function of its solid angle. Convexity arguments then show that the sum of all the cone volume bounds is minimized when there are 13 faces each of solid angle 4π/13.     

Representing polyhedra: faces are better than vertices

This paper investigates the reconstruction of planar-faced polyhedra given their spherical dual representation. The spherical dual representation for any genus 0 polyhedron is shown to be unambiguous and to be uniquely reconstructible in polynomial time. It is also shown that when the degree of the spherical dual representation is at most four, the representation is unambiguous for polyhedra of any genus. The first result extends, in the case of planar-faced polyhedra, the well known result that a vertex or face connectivity graph represents a polyhedron unambiguously when the graph is triconnected and planar. The second result shows that when each face of a polyhedron of arbitrary genus has at most four edges, the polyhedron can be reconstructed uniquely. This extends the previous result that a polyhedron can be uniquely reconstructed when each face of the polyhedron is triangular. As a consequence of this result, faces are a more powerful representation than vertices for polyhedra whose faces have three or four edges. A result of the reconstruction algorithm is that high level features of the polyhedron are naturally extracted. Both results explicitly use the fact that the faces of the polyhedron are planar. It is conjectured that the spherical dual representation is unambiguous for polyhedra of any genus.     

Positivity of curvature and convexity of faces

Two-dimensional polyhedra homeomorphic to closed two-dimensional surfaces are considered in the three-dimensional Euclidean space. While studying the structure of an arbitrary face of a polyhedron, an interesting particular case is revealed when the magnitude of only one plane angle determines the sign of the curvature of the polyhedron at the vertex of this angle. Due to this observation, the following main theorem of the paper is obtained: If a two-dimensional polyhedron in the three-dimensional Euclidean space is isometric to the surface of a closed convex three-dimensional polyhedron, then all faces of the polyhedron are convex polygons.     

On the difficulty of triangulating three-dimensional Nonconvex Polyhedra

A number of different polyhedraldecomposition problems have previously been studied, most notably the problem of triangulating a simple polygon. We are concerned with thepolyhedron triangulation problem: decomposing a three-dimensional polyhedron into a set of nonoverlapping tetrahedra whose vertices must be vertices of the polyhedron. It has previously been shown that some polyhedra cannot be triangulated in this fashion. We show that the problem of deciding whether a given polyhedron can be triangulated is NP-complete, and hence likely to be computationally intractable. The problem remains NP-complete when restricted to the case of star-shaped polyhedra. Various versions of the question of how many Steiner points are needed to triangulate a polyhedron also turn out to be NP-hard.This work was supported by National Science Foundation Grant CCR-8809040.     

Uniqueness of least area surfaces in the 3-torus

Given any -periodic metric g on and a plane through the origin, Bangert [4] shows that there exists a properly embedded surface homeomorphic to which is homotopically area-minimizing w.r.t. g, lies in a strip of bounded width around P, and does not have self-intersections when projected to the 3-torus . For the set of such surfaces, we show the following uniqueness theorems: If P is irrational, i.e., is not spanned by vectors in , the action of on by translations has a unique minimal set. If P is totally irrational, i.e., , then the surfaces in are pairwise disjoint. Received: 8 July 1999 / In final form: 14 February 2000 / Published online: 25 June 2001     

Grid Vertex-Unfolding Orthogonal Polyhedra

An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a net, a connected planar piece with no overlaps. A grid unfolding allows additional cuts along grid edges induced by coordinate planes passing through every vertex. A vertex-unfolding allows faces in the net to be connected at single vertices, not necessarily along edges. We show that any orthogonal polyhedra of genus zero has a grid vertex-unfolding. (There are orthogonal polyhedra that cannot be vertex-unfolded, so some type of “gridding” of the faces is necessary.) For any orthogonal polyhedron P with n vertices, we describe an algorithm that vertex-unfolds P in O(n ²) time. Enroute to explaining this algorithm, we present a simpler vertex-unfolding algorithm that requires a 3×1×1 refinement of the vertex grid. This is a significant revision of the preliminary version that appeared in [2]. J. O’Rourke’s research was supported by NSF award DUE-0123154.     

Hegaard diagrams and colored polyhedra

The main result is a construction, which transforms an irreducible Hegaard diagram of genus h of a closed three-dimensional manifold into a colored polyhedron with 2h faces, which determines the manifold. It is also shown that for any irreducible manifold of genus h there exists a polyhedron with 2h faces, for which the factorization map is an immersion. An algorithm similar to Neuwirth's algorithm is constructed.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 66, pp. 180–188, 1976.     

On some properties of 4-regular plane graphs

The d-distance face chromatic number of a connected plane graph is the minimum number of colors in such a coloring of its faces that whenever two distinct faces are at the distance at most d, they receive distinct colors. We estimate 1-distance chromatic number for connected 4-regular plane graphs. We show that 0-distance face chromatic number of any connected multi-3-gonal 4-regular plane graphs is 4. © 1995, John Wiley & Sons, Inc.     

On the problem of the finiteness of the number of the combinatorial types of infinite convex polyhedra with equiangular faces

An infinite (complete) convex polyhedron with equiangular faces, that is, such that all the angles of each of its faces are equal to one another, is called irreducible if the number of monogonal faces belonging to it cannot be decreased (by identifying their sides) while preserving the equiangularity of all of the other faces and the convexity of the polyhedron itself (a lack of conditional edges). Any infinite convex polyhedron with equiangular faces can be obtained from the corresponding irreducible one by pasting in the missing number of monogons. It is proved that the number of combinatorially different irreducible polyhedra is finite, not counting three infinite series of frusta of cones with finite or infinite bases and right prisms with infinite bases. It is also established that, without exception, all infinite convex polyhedra with equiangular faces and total curvature 2are the derivatives of closed convex polyhedra with equiangular faces. The proof is carried out with the help of A. D. Milka's method from Ross. Zh. Mat., 1988, 3A830. Translated from Ukrainskii Geometricheskii Sbornik, No. 35, pp. 75–83, 1992.