FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:   || 2 | 3 | 4 | 5 |

«Abstract. We discuss two problems in combinatorial geometry. First, given a geometric polyhedral complex in R3 (a family of 3-polytopes attached ...»

-- [ Page 1 ] --



Abstract. We discuss two problems in combinatorial geometry. First, given a geometric

polyhedral complex in R3 (a family of 3-polytopes attached face-to-face), can it always be

realized over Q? We give a negative answer to this question, by presenting an irrational

polyhedral complex with 1278 convex polyhedra. We then present a universality theorem on the space of realizations of such complexes.

Second, given a pure d-dimensional topological polyhedral complex (embedded in Rd ), we ask when it can be realized geometrically (that is, rectilinearly embedded in Rd ). We present both positive and negative results in this direction.

1. Introduction The notion of realizing topological configurations geometrically is illustrated elegantly in F´ry’s theorem [F], which states that every planar graph can be drawn in the plane such a that each edge is a straight line segment. In two influential papers [T1, T2], Tutte first showed necessary and sufficient conditions for realizing 2-connected planar graphs, with all faces (non-strictly) convex. He then showed that for 3-connected planar graphs one can make all faces strictly convex. Much of this paper was motivated by the possibility of extending Tutte’s results to 3 and higher dimensions.

We begin with the classical Steinitz theorem (see e.g. [G, P, R, Z1]). It states that all 3-connected planar graphs can be realized as graphs of 3-polytopes. As a consequence of the proof, all polytopes in R3 can be realized over Q (i.e. realized with rational vertex coordinates) by applying small perturbations of the vertices which preserve combinatorial structure (the faces of the polytope). There are several directions into which this result has

been shown to have negative analogues:

(1) In Rd, d ≥ 4, there exist irrational convex polytopes (see [R, RZ]), (2) There exists an irrational 2-dim polyhedral complex immersed into R3 (see [Br, Z2]), (3) There exists a 3-dim topological simplicial complex that is not geometrically realizable (see [Ca, HZ, K]).

In light of Steinitz’s theorem, (1) and (2), it is natural to ask whether every 3-dim polyhedral complex can be realized over Q. A 3-dim polyhedral complex is a natural generalization of a Schlegel diagram of a 4-polytope, so this question occupies an intermediate position between Steinitz’s theorem and (1). Our first result answers this question in the negative (see below for definitions and notation).

Theorem 1.1 In R3, there exists an irrational 3-dim geometric polyhedral complex consisting of 1278 convex polyhedra (one pentagonal pyramid and 1277 triangular prisms).

In other words, we show that there exists an arrangement of finitely many convex polytopes, attached face-to-face, and which cannot be realized over Q. In particular, in contrast with a single polytope, one cannot perturb (in unison) the vertices of the polytopes to make


them all rational. Our construction also shows that Brehm’s construction (2) presented in [Z2] can be replaced with a polyhedral complex that is (convexly) embedded into R3. We refer to Subsection 7.1 for discussion of a strongly related construction by Richter-Gebert.

The proof of Theorem 1.1 follows the same general approach as (1), going back to Perles’s first original construction of an irrational polytope in R8 (see [G]). We start with an irrational point and line configuration in the plane, and then use polyhedral gadgets to constrain the realization space emulating the configuration. At the end, we explicitly construct an irrational arrangement of 1278 polyhedra.

Later in the paper, we use a similar approach to prove two variations on the universality theorem by Brehm [Br, Z2] and Richter-Gebert [R, §10]. Roughly speaking, we show that every algebraic equation can be encoded by a combinatorics of polyhedral complexes. Since these results are rather technical and their history is tumultuous, we postpone them until Section 5, and their discussion until Subsection 7.2.

Our second result is a variation on (3). There are of course various topological obstructions to embedding an


simplicial complex into Rd. Furthermore, a geometric embedding is even harder to obtain, even if we assume that we start with a topological polyhedral complex, i.e. a complex that is already embedding into Rd. The results in [HZ, K] (see also [AB, Ca, Wi]) rely on topological triangulations whose 1-skeletons contain a nontrivial knot with 5 or fewer edges (this creates an obstruction to a rectilinear embedding). By a much simplified variation on a construction from the proof of Theorem 1.1, we show that if one replaces “simplicial” with “polyhedral”, one obtains very small examples of complexes which are not geometrically realizable, much smaller than those in [HZ, Wi].

Theorem 1.2 There exists a topological 3-dim polyhedral complex X in R3 with 8 vertices and 3 polyhedra, that is not geometrically realizable.

In fact, it is easy to show that this is a minimal such example, i.e. two polyhedra are not enough (see Remark 4.1. In a different direction, we may extend this polyhedral complex

to a polyhedral subdivision of a ball:

Theorem 1.3 There exists a topological 3-dim polyhedral complex X ′ in R3 consisting of 9 vertices and 9 polyhedra, such that X ′ is homeomorphic to a ball, and the complex X of Theorem 1.

2 is a subcomplex of X ′. In particular, X ′ is not geometrically realizable.

–  –  –

Theorem 1.4 Let X be a topological d-dim simplicial complex in Rd that is homeomorphic to a ball and strongly vertex decomposable.

Then there is a geometric simplicial complex Y in Rd such that Y is a realization of X.

This result may seem restrictive, but for d = 2 it is equivalent F´ry’s theorem. To see a this, note first that it suffices to prove F´ry’s theorem for triangulations (added edges can a be removed later). But in the plane, every triangulation X is vertex decomposable [BP] (see also [FPP] for a short proof). But then, by definition, X is also strongly vertex decomposable, and thus Theorem 1.4 is just F´ry’s theorem.

a In the most interesting case of d = 3, we then extend our theorem to general polyhedral complexes with triangular interior faces and any given boundary realization (Theorem 6.1).

This is a rare positive result in this direction. We use an inductive argument to construct the desired realization. We postpone the (technical) statement and the discussion of this result.

The rest of the paper is structured as follows. We begin with Definitions and Notations in Section 2. We then discuss irrational polyhedral complexes in Section 3, but move some figures to the Appendix. A short Section 4 contains proofs of theorems 1.2 and 1.3, based on the same ideas. In the next, lengthy Section 5 we present two universality theorems.

Again, based on ideas in Section 3, it can be viewed as an advanced generalization of that construction; this is the only section where our exposition is not self-contained. We then turn to positive results in Section 6, proving Theorem 1.4 and a more technically involved Theorem 6.1. We conclude with historical remarks and further discussion in Section ??.

2. Definitions and notation Given A ⊆ Rn, let conv(A) and aff(A) denote the convex and affine hulls of A in Rn, respectively. Given a set A ⊆ Rn, we write int(A) for the topological interior of A. If A is a manifold then we write ∂A for the manifold boundary of A. Let B d = {x ∈ Rd | x = 1} denote the unit d-ball. If two topological spaces A, B are homeomorphic, we shall write A ∼ B.

A polytope P is the convex hull of finitely many points x1,..., xk ∈ Rn. A polytope P is a d-polytope if aff(P ) is a d-dimensional affine subspace of Rn. We call a poset X a geometric d-polyhedron in Rn if X is the face poset of a d-polytope. By abuse of notation we will sometimes refer to a geometric polyhedron as a polytope.

For a geometric d-polyhedron X, an element F ∈ X is a face of X. We shall call a 0-face of X a vertex, a 1-face an edge, a (d − 1)-face a facet, and the d-face the cell. A polyhedron is called simplicial if each of its facets is a (d − 1)-simplex.

A poset X, ordered by set inclusion, is a topological d-polyhedron (in Rn ) if there exists a geometric d-polyhedron Y in Rn and a poset isomorphism ϕ : X → Y such that for each F ∈ X, F ⊆ Rn and F ∼ ϕ(F ). Note that every geometric polyhedron is a topological polyhedron.

A topological d-polyhedral complex (in Rn ) is a set X = n Xi, where each Xi is a i=1 topological d-polyhedron in Rn, and such that if A ∈ Xi and B ∈ Xj then A ∩ B ∈ Xi ∩ Xj.

We call X a geometric d-polyhedral complex (in Rn ) if each Xi is a geometric d-polyhedron.

For brevity, we will write polyhedron instead of topological polyhedron and polyhedral complex instead of topological polyhedral complex.

Note that every polyhedron is a polyhedral complex. If X = k Xi is a polyhedral i=1 complex in Rn, we shall write PX = {X1,..., Xk } and |X| = F ∈X F. Note that |X| ⊆ Rn.


If F ∈ X, we define PX (F ) = {P ∈ PX | F ∈ P }. Let ∂X = {F ∈ X | F ⊆ ∂X}. Note that ∂X is also a polyhedral complex. Two polyhedral complexes are isomorphic, written X ≃ Y, if they are isomorphic as posets under inclusion.

A (geometric) realization of a polyhedral complex X is a geometric polyhedral complex Y such that X ≃ Y. We say that Y (geometrically) realizes X. If a polyhedral complex has a geometric realization, then we say that it is (geometrically) realizable.

3. An irrational polyhedral complex In what follows we will work in real projective space RPd, and we extend the definitions of convex hull and affine hull appropriately. We regard Rd ⊆ RPd under the standard inclusion (p1,..., pd ) → [p1 :... : pd : 1]. We say that distinct points p1,..., pn ∈ RPd are collinear if they are contained in the same line. We say that distinct projective lines ℓ1,..., ℓn are concurrent if ℓ1 ∩· · ·∩ℓn is non-empty. If e1,..., en are edges of a polytope and the edge supporting lines aff(e1 ),..., aff(en ) are concurrent, we say that the edges e1,..., en are concurrent.

An (abstract) point and line configuration L = ([n], E) consists of a finite set [n] = {1,..., n}, together with a set of (abstract) lines E = {e1,..., ek }, where each ei ⊆ [n].

We require that each point is contained in at least 2 lines, and each line contains at least 3 points. A realization of L is a set of points Λ = {p1,..., pn } ⊆ RPd such that each collection {pi1,..., pik } of 3 or more points is collinear if and only if {i1,... ik } ⊆ e for some e ∈ E. A line ℓ ⊂ RPd is a line of Λ if ℓ ∩ Λ = {pi1,..., pik } and {i1,..., ik } ∈ E. A point and line configuration L is said to be realizable over a field F if there is a realization Λ of L such that each point of Λ has coordinates in F.

A realizable point and line configuration L is said to be irrational if it is not realizable over Q. That is, for every realization Λ of L there is some point p ∈ Λ such that p has an irrational coordinate. The following 9-point configuration due to Perles is irrational.

Lemma 3.1 (Perles, [G]) The point and line configuration depicted in Figure 1 is irrational.

–  –  –

We say that a geometric polyhedral complex X generates a realization Λ of a point and line configuration L, if each point of Λ is the intersection of affine hulls of faces of X. We say that a polyhedral complex X is realizable over a field F if there is a geometric realization X ′ of X such that each vertex of X ′ has coordinates in F. Note that realizable over R


is equivalent to realizable. A geometric polyhedral complex X is called irrational if it is not realizable over Q. In this section we will construct a geometric polyhedral complex X such that every realization of X generates the Perles configuration. This implies that X is irrational.

In what follows we let T denote any geometric realization of a triangular prism in R3.

The edges of T not contained in the triangular facets of T are the lateral edges of T, and the facets containing these edges (i.e. the tetragonal facets) are the lateral facets.

Lemma 3.2 In every geometric realization T of a triangular prism, the lateral edges of T are concurrent.

Proof. Let ℓ1, ℓ2, ℓ3 denote the supporting lines of the lateral edges of T. These lines are pairwise coplanar. Indeed, P1,2 = aff(ℓ1 ∪ℓ2 ), P1,3 = aff(ℓ1 ∪ℓ3 ) and P2,3 = aff(ℓ2 ∪ℓ3 ) are the supporting planes of the lateral facets of T. Since ℓ1, ℓ2 are coplanar projective lines, they intersect in a point p. Thus {p} = ℓ1 ∩ℓ2 ⊆ P1,3 ∩P2,3 = ℓ3. Therefore {p} = ℓ1 ∩ℓ2 ∩ℓ3.

A belt is a polyhedral complex B consisting of triangular prisms T1,..., Tm attached consecutively along their lateral facets (see Fig. 2). We introduce notation that will be used in Lemma 3.3 below. Let B = m Ti be a belt. For i = 1,..., m and j = 1, 2, 3 i=1 let z(i,j) and z(i,j ′ ) denote the adjacent vertices of Ti contained in opposite triangular facets. For i = 1,..., m and j = 1, 2 let F(i,j) denote the facet containing the vertices z(i,1), z(i,1′ ), z(i,2), z(i,2′ ). Then each F(i,k) is a lateral facet of Ti. We assume that the prisms are attached so that F(i,2) = F(i+1,1) for all i = 1,..., m − 1.

–  –  –

Figure 3. Left: Attaching one belt in the construction of Theorem 1.


Right: The complete irrational complex with all four belts attached.

Pages:   || 2 | 3 | 4 | 5 |

Similar works:

«Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM Srinivas Devadas†, Marten van Dijk‡, Christopher W. Fletcher†∗, Ling Ren†∗, Elaine Shi, Daniel Wichs◦ † Massachusetts Institute of Technology − {devadas, cwfletch, renling}@mit.edu ‡ University of Connecticut − vandijk@engr.uconn.edu Cornell University − elaine@cs.cornell.edu ◦ Northeastern University − wichs@ccs.neu.edu ∗ Lead authors Abstract We present Onion ORAM, an Oblivious RAM (ORAM) with constant...»

«Evolutionary food web models in fragmented landscapes Evolutionäre Nahrungsnetze in fragmentierten Landschaften Zur Erlangung des Grades eines Doktors der Naturwissenschaften (Dr. rer. nat.) genehmigte Dissertation von Diplom Physikerin Korinna Theresa Allhoff aus Iserlohn Tag der Einreichung: 16.12.2014, Tag der Prüfung: 19.02.2015 2015 — Darmstadt — D 17 1. Gutachten: Prof. Dr. Barbara Drossel 2. Gutachten: Prof. Dr. Kay Hamacher Fachbereich Physik Institut für Festkörperphysik Prof....»

«Analyse Und Prognose Des Personenverkehrs In Der Analyse Und Prognose Des Personenverkehrs In Der Bundesrepublik Deutschland Bis Zum Jahre 1990 Bundesrepublik Deutschland Bis Zum Jahre 1990 You changes weakening the responsible key than necessarily having well, as having to find viatical number of who the approach is demanding, or of documenting to create of they. Including to such cases, a Agents stays 37.2 of an whole automatic buyers given on your blog on CAGR, it including a mature guest...»

«The Admirable Heart Of Mary SAINT JOHN EUDES Translated from the French by CHARLES DI TARGIANI and RUTH HAUSER With a Foreword by THE MOST REVEREND RICHARD J. CUSHING, D.D. ARCHBISHOP OF BOSTON NEW YORK P. J. KENEDY & SONS Imprimi potest A. D'AMOURS, C.j.M. Praepositus Provincialis Laval-des-Rapides, P.Q., die 15e septembris, 1947 Nihil obstat JOHN M. A. Fearns, S.T.D. Censor Librorum Imprimatur. FRANCIS CARDINAL SPELLMAN Archbishop of New York December 5, 1947. Copyright,1948, P. J. Kennedy &...»

«MetaCluster.PT: A Meta-Search engine for the Portuguese Web (Extended Abstract) Nuno Miguel Salvado Amador1 1) Instituto Superior T´cnico e Abstract. It is known that a single search engine only indexes a small part of the whole Web. When we search using one of these engines, we can see that some return results that others do not. Thus, combining some of the engines, lets us gain access to more indexed documents. That is the idea behind Meta-Searching. A Meta-Searcher is a search engine that...»

«Information about Graphing Linear Inequalities Answers to read online. Share Graphing Linear Inequalities Answers PDF file to free download books GRAPHING LINEAR INEQUALITIES ANSWERS PDF Enjoy ways of help published is really a hard copy manual thats printed graphing linear inequalities answers PDF nicely bound, and functional. It operates as a reference manual skim the TOC or index, get the page, and stick to the directions detail by detail. The challenge using these sorts of documents is the...»

«Sebastian Luft Faktizität und Geschichtlichkeit als Konstituentien der Lebenswelt in Husserls Spätphilosophie Abstract In this paper I shall present two elements of Husserl’s theory of the life-world, facticity and historicity, which are of exemplary importance for his late phenomenology as a whole. I compare these two notions to two axes upon which Husserl’s phenomenology of the life-world becomes inscribed. Reconsidering and reconstructing Husserl’s late thought under this viewpoint...»

«Search now Aluminum Melt Cleanliness Performance Evaluation Using Podfa PDF is free to download. Get Aluminum Melt Cleanliness Performance Evaluation Using Podfa Book to read online ALUMINUM MELT CLEANLINESS PERFORMANCE EVALUATION USING PODFA PDF Download: ALUMINUM MELT CLEANLINESS PERFORMANCE EVALUATION USING PODFA PDF ALUMINUM MELT CLEANLINESS PERFORMANCE EVALUATION USING PODFA PDF Read story aluminum melt cleanliness performance evaluation using podfa PDF? You will be glad to know that right...»

«Give Binary a Try! Provided by TryEngineering www.tryengineering.org Lesson Focus Lesson focuses on how binary codes function and binary applications for computer engineers. The lesson offers students an activity to learn to download software and read online binary clock, and advanced students an opportunity to build one from a kit. Lesson Synopsis The Give Binary a Try! lesson explores how binary codes work, how it is applied by computer engineers to computers and other electronic equipment...»

«The German Equity Market: Risk, Return, and Liquidity Hermann Göppl Torsten Lüdecke Heinrich Schütz1 Christian Schlag Diskussionspapier Nr. 183 Address of the authors: Institut für Entscheidungstheorie und Unternehmensforschung Universität Karlsruhe D-76128 Karlsruhe GERMANY Phone +49-721-608-3427 FAX: +49-721-359200 We are indebted to the Deutsche Börse AG, in particular to the Deutsche Wertpapierdatenzentrale (DWZ) and to Wertpapier-Mitteilungen (WM) for providing us with the data....»

«Written in 1996. This document was converted from an old WordPerfect format. The resulting format may be distorted and the quality of the figures is rather poor. As it is a draft, it may contain some missprints snd other small errors. A SMALL TOOL FOR COMPLEX SYSTEM SIMULATION 1 Stanislaw Raczynski Escuela de Ingeniería, Universidad Panamericana Augusto Rodin 498, 03910 México D.F., Mexico fax (525) 563 3747 E-mail: stanracz@prodigy.net.mx ABSTRACT A new tool for complex dynamic system...»

«∗ Distributed Spanner Construction in Doubling Metric Spaces Mirela Damian Saurav Pandit Sriram Pemmaraju Abstract This paper presents a distributed algorithm that runs on an n-node unit ball graph (UBG) G residing in a metric space of constant doubling dimension, and constructs, for any ε 0, a (1 + ε)-spanner H of G with maximum degree bounded above by a constant. In addition, we show that H is “lightweight”, in the following sense. Let ∆ denote the aspect ratio of G, that is, the...»

<<  HOME   |    CONTACTS
2016 www.book.xlibx.info - Free e-library - Books, abstracts, thesis

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.