FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:     | 1 |   ...   | 2 | 3 || 5 |

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

-- [ Page 4 ] --

Given a d-polyhedron X in Rn and a facet F ∈ X, the Schlegel set of X with respect to F, which we denote by ξ(X, F ), is the closed convex set bounded by the hyperplanes aff(F ) and aff(Gi ) for each facet Gi strongly adjacent to F. That is, if G1,..., Gk ∈ X denote the facets strongly adjacent to F, HGi denotes the closed halfspace bounded by aff(Gi ) and meeting the interior of X, and HF denotes the closed halfspace bounded by aff(F ) and not meeting the interior of X, then ξ(X, F ) = HF ∩ k HGi. A Schlegel point is a point i=1 y ∈ int(ξ(X, F )).

If the facet F is a (d− 1)-simplex, the hyperplanes aff(Gi ) intersect in a (possibly infinite) point, which we call the apex of ξ(X, F ). If the apex x is a finite point, then x ∈ ξ(X, F ) if and only if x and X lie on opposite sides of the hyperplane aff(F ). If x is a finite point and x ∈ ξ(X, F ), then ξ(X, F ) is just the cone with base F and apex x.

Theorem 6.1 Let d ≤ 3 and let X be a topological d-polyhedral complex in Rd such that |X| ∼ B d and all interior facets F ∈ X − ∂X are simplices.

If X is vertex truncatable, then there is a geometric polyhedral complex Y in Rd such that X ≃ Y. Furthermore, we may choose Y to have all vertices rational.

We prove in fact a stringer result, that such as embedding exists for every given embedding of ∂X. It is important to emphasize that this is a much stronger property, which does not extend to conditions of Theorem 1.4 (see Subsection ??).

Proof. To prove the theorem, we strengthen it, which in turn strengthens our induction

hypothesis. Namely, we claim that if such a Y exists, then furthermore:

(i) For any polytope Z such that ∂Z ≃ ∂X, we may choose Y such that |Y | = |Z|.

(ii) Let ǫ 0. Let X1,... Xk ∈ PX such that Xi ∩ Xj ⊆ ∂X and Xi ∩ ∂X is a facet of X, call it Fi. Let Yi ∈ PY be the polyhedron corresponding to Xi and let Gi ∈ ∂Y be the face corresponding to Fi ∈ ∂X. Then we may choose Y such that α(Hj, Gi ) ǫ for all i = 1,..., k and every face Hj ∈ Yi strongly adjacent to Gi.

–  –  –

on the number n of vertices of X. In the base case X has d + 1 vertices, and we may take Y to be any geometric d-simplex in Rd. Now suppose n d + 1.

Since X is vertex truncatable, choose a boundary vertex w0 satisfying either condition (b) or (c) of the definition. Let X ′ = X ∗ (w0 ) w0. By definition, X ′ is vertex truncatable, so in particular |X ′ | ∼ B d. Furthermore, all interior facets of X ′ are clearly simplices.

Let Z be a polytope such that ∂Z ≃ ∂X. If d = 3, such a polytope Z exists by Steinitz’s Theorem. If d = 2 then Z may be any strictly convex polygon with the same number of boundary vertices as X. Since w0 is boundary minimal, it has d neighbors w1,..., wd in ∂X. Let v0 denote the vertex of Z corresponding to w0. For each i = 1,..., d, the vertex wi corresponds to a vertex vi of Z, where vi is a neighbor of v0. The vertices vi lie on a hyperplane H = aff(v1,..., vd ). The hyperplane H splits Z into two polytopes Q1, Q2, each defined by taking all faces of Z lying on a given side of H, which includes the facet TZ = conv(v1,..., vd ) in both cases. One of these two polytopes, say Q1, contains v0. Then note that Q1 is a d-simplex.

Clearly |lkX ∗ (w0 ) (w0 )| is homeomorphic to a (d − 1)-ball. So if d = 3 then lkX ∗ (w0 ) (w0 ) is isomorphic to the Schlegel diagram of some 3-polytope by Steinitz’s theorem. Call this polytope A. If d = 2 then we may simply take A to be a convex polygon with one more edge than lkX ∗ (w0 ) (w0 ). Let u1,..., ud be the vertices of A corresponding to the vertices v1,..., vd of lkX ∗ (w0 ) (w0 ), and let TA = conv(u1,..., ud ). Note that TA is a (d − 1)-simplex, and a facet of A. Apply an affine transformation to |A| so that TA = TZ. If A is not a simplex, apply a projective transformation to |A| that fixes TA and takes the apex x of ξ(A, TA ) to a finite point on the side of the hyperplane aff(TA ) not containing |A|.

For a set S ⊆ Rd, let (S, 1) = {(x, 1) ∈ Rd × R | x ∈ S}. Form the (d + 1)-cone C with base (|A|, 1) and apex a ∈ Rd+1, ad+1 = 1. Let FC denote the (clearly simplicial) d-face of C containing a and (TA, 1). Let W denote the Schegel projection of C onto its facet FC, with respect to a Schlegel point y. Then W is a geometric polyhedral complex. Clearly W contains a subcomplex B such that B ≃ A. Since (TA, 1) ⊆ FC, the (d − 1)-face (TA, 1) is fixed by the Schlegel projection, so in fact (TA, 1) ∈ B is the face of B corresponding to TA ∈ A. Apply an affine transformation to |W | that maps (TA, 1) to TA = TZ and maps a to v0. This transforms |B| accordingly. In particular, we now have |W | = |Q1 |. Thus Z ′ = B#TZ Q2 is a polytope such that ∂Z ′ ≃ ∂X ′.

By the induction hypothesis and (i), since X ′ contains one fewer vertex than X, there is a geometric polyhedral complex Y ′ such that X ′ ≃ Y ′ and |Y ′ | = |Z ′ |. Let Y ∗ = Y ′ ∪ W.

Then clearly X ∗ (w0 ) ≃ Y ∗. Removing the facets of Y ∗ corresponding to the facets τ (w0, P ) of X ∗ (w0 ), we obtain a polyhedral complex Y such that X ≃ Y and |Y | = |Z|. This establishes (i), provided that each cell of Y is convex. We now show that this is the case.

Let X1,..., Xk ∈ PX ′ denote the d-polyhedra of X ′ such that |Xi′ | ⊆ |X| for some ′ ′ X ∈ PX (w0 ). We will let Xi denote the unique d-polyhedron of X such that |Xi′ | ⊆ |Xi |.

For all i, j = 1,..., k, since w0 ∈ Xi ∩ Xj and X is a polyhedral complex, we must have Xi′ ∩ Xj ⊆ ∂X ′, for otherwise Xi and Xj would intersect in more than a unique common ′ face. If w0 is a strong solitary vertex of X, then k = 1. Thus the single polyhedron Y1 ∈ PY corresponding to X1 is clearly convex from the above construction.

Now suppose that w0 is a strong shedding vertex of X. Note that any shedding vertex w0 of X must satisfy cstX (w0 ) ∩ ∂X = cst∂X (w0 ), for otherwise |X w0 | would not be homeomorphic to B d. Thus we must have Xi′ ∩ ∂X ′ = τ (w0, Xi ). So X1,... Xk satisfy ′ ′ the hypotheses of (ii). Let Yi′ ∈ PY ′ be the polyhedron corresponding to Xi′ and Gi ∈ Y ′ the facet corresponding to τ (w0, Xi ). Let Yi ∈ PY be the unique polyhedron such that |Yi′ | ⊆ |Yi |. Since our induction hypothesis is enhanced by (ii), we may assume that the 22 IGOR PAK, STEDMAN WILSON angles α(Hj, Gi ) are arbitrarily small for each i and each face Hj ∈ Yi′ strongly adjacent to Gi. Since the cells |Yi′ | are convex by induction and form arbitrarily small angles with Gi, we may ensure that on removing Gi the resulting cell |Yi | ∈ Y is convex. Finally, if σ ∈ Y is a cell not having any of the |Yi′ | as a subset, then either σ is a d-simplex (hence convex) or σ ∈ Y ′. In the latter case σ is convex because Y ′ is a geometric polyhedral complex.

Now we must show that (ii) holds. Let X1,..., Xℓ ∈ PX be a collection of polytopes satisfying the hypotheses of (ii), and let Y1,... Yℓ ∈ PY denote the corresponding polytopes of Y. If Yi ∈ PY ′ then we obtain the conclusion of (ii) from the induction hypothesis.

Now suppose Yi ∈ PY ′. Then Yi ∈ PW. If the A in the above construction is a simplex, / then ℓ = 1. Let v be the vertex of A not contained in TA. Then we may clearly choose v arbitrarily close to the facet Yi ∩ ∂Y. If A is not a simplex, then because the point x is finite and lies on the side of aff(TA ) opposite to that of A, x ∈ ξ(C, FC ). In particular ξ(C, FC ) is a cone with base FC and apex x ∈ Rd+1. By choosing the Schlegel point y in the above construction arbitrarily close to x, we may ensure that all such angles α(Fi, Fj ) in the projection W are arbitrarily small.

Finally, that Y may be chosen to be rational is an immediate consequence of the methods of the proof. Broadly speaking, we obtained Y by first using Steinitz’s theorem to produce polytopes Z and A, and then manipulating these polytopes using projective transformations.

But from the proof of Steinitz’s theorem, we may take both Z and A to be rational. By then using only rational affine and projective transformations in the above constructions, we may in fact obtain a rational geometric polyhedral complex Y such that X ≃ Y.

It is straightforward to show that all 2-polyhedral complexes are vertex truncatable. Thus Theorem 6.1 implies that all 2-polyhedral complexes are geometrically realizable. Note that every 2-polyhedral complex is a 2-connected plane graph. However, the converse is not true.

In fact, if a 2-connected plane graph is not a polyhedral complex (i.e. if the intersection of two faces is more than a unique common edge or vertex of both), then it clearly does not admit an embedding such that all faces are strictly convex.

Therefore we obtain necessary and sufficient conditions for a 2-connected plane graph G to admit an isotopic embedding G′ such that all faces of G′ are strictly convex. Specifically, a 2-connected plane graph G has a strictly convex isotopic embedding if and only if G is a 2-polyhedral complex. From this we recover Tutte’s theorem [T1].

Finally, we note that the condition d ≤ 3 in the statement of Theorem 6.1 plays a crucial role. Namely, it allows us to invoke Steinitz’s theorem (for d = 3). For example, by Steinitz’s theorem a simplicial 2-sphere is always isomorphic to the boundary of a 3-polytope. In higher dimensions the analogous statement is not true (see [GS]).

7. Further discussion

7.1. It is perhaps not obvious why Theorem 1.1 does not follow from existence of irrational 4-polytopes. Indeed, one can take a Schlegel diagram Q of an irrational 4-polytope P and conjecture that this is the desired irrational polyhedral complex. The logical fallacy here is that the implications go the other way. If the Schlegel diagram of P is irrational, then indeed P must be an irrational polytope. However, the converse is not true. There is no reason why all realizations of the Schegel diagram Q must have irrational coordinates, even if P is irrational. In fact, after computing degrees of freedom one should expect additional realizations of Q. Similarly, it is only in R3 that one can have (and does have) the MaxwellCremona theorem [R]; in R4 and higher dimensions it easily fails in full generality (cf. ??).


On the other hand, it was noted by Richter-Gebert [?, §10] that the polytope operations used in the construction of irrational polytopes can be emulated in R3 by an analogous operations on the level of Schegel diagram.1 Richter-Gebert briefly outlined both an irrational construction and a universality type theorem. If completed, the former construction would prove smaller than out 1278 polytope construction in Theorem 1.1, but each polytope is more complicated. The latter (universality result), is of a different nature from Theorem 5.5 as no intersections are allowed. As stated, it would imply only the first part of Theorem 5.2 (and only if the outside face is a tetrahedron), since we allow only triangular prisms as our polyhedra.

7.2. Let us here address a delicate issue of Brehm’s universality theorem, as outlined in [Br, Z2]. Our Theorem 5.5 is clearly a variation on Brehm’s announced result. In fact, the proof ideas do not seem very far from ours, even if different on a technical level. Unfortunately, the Brehm’s complete proof has never appeared, and from our experience with universality type theorems these details are occasionally delicate and important. Thus, one can view our work as either an application of our tools to re-derive Brehm’s results, or the first complete proof of a theorem of this type. Since in fact our construction has further properties is an unexpected bonus.

Let us mention that allowing intersections in our proof of Theorem 5.5 as the belts can get linked and knotted in a non-trivial way, a possibility we cannot account without further sub-triangulating the construction.

7.3. There is a rather simple reason why Tutte’s theorems are delicate and unlikely to allow a direct extension to higher dimensions, even ignoring the topological obstructions as in the paper. Consider the first two graphs as in Figure 11 below. The smaller of the two has a non-strict convex realization, while the bigger does not. Tutte’s result is “if and only if”, and he explains that the difference between the two is a combinatorial rather than geometric or topological reason. Now of course, neither have a (strict) convex realization.

This can be explained from the fact that this graph is not 3-connected and thus its spring embedding collapses. But in R3 if one replaces the middle square with an octahedron, the connectivity obstacle disappears.

–  –  –

7.4. The vertex truncatability condition in Theorem 1.4 is somewhat restrictive already in R3. For example, it cannot apply to any triangulation of the octahedron or the icosahedron since their boundaries have no vertices of degree three.

Recall now that the inductive assumption in the proof of Theorem 1.4 implied that the boundary can be prescribed in advance. Now the study of triangulations of the octahedron shows that vertex truncatability is critical for the result. Consider an octahedron Q = (11′ 22′ 33′ ) with topological triangulation (122′ 3), (122′ 3′ ), (1′ 233′ ), (1′ 2′ 33′ ), and (22′ 33′ ).

In this triangulation, the triangles (122′ ) and (1′ 33′ ) are not linked (topologically). But this is false for some realizations of Q. This means that Theorem 1.4, at least a stronger version where the boundary is prescribed, cannot possibly be extended to triangulations as simple as this one.

Interestingly, one can easily see why the “linked triangle obstacles” never appears in our situation. That is because the vertex truncatability condition forbids all diagonals, defined as inner edges connecting two boundary vertices. This follows easily by induction.

Finally, let us mention that we do not believe that Theorem 1.4 extends to d ≥ 4. It would be interesting to find such a counterexample.

7.5. It is obvious that the triangulation produced in Theorem 1.4 can be made rational:

Pages:     | 1 |   ...   | 2 | 3 || 5 |

Similar works:

«Access download Kuta Software Infinite Geometry Similar Triangles Answers in here. Also read document Kuta Software Infinite Geometry Similar Triangles Answers online KUTA SOFTWARE INFINITE GEOMETRY SIMILAR TRIANGLES ANSWERS PDF General ways of help documentation is really a hard copy manual that's printed kuta software infinite geometry similar triangles answers nicely bound, and functional. It operates as a reference manual skim the TOC or index, get the page, and stick to the directions...»

«DOCUMENT RESUME ED 360 776 EC 302 348 AUTHOR Spencer, Patricia E.; Kelly, Arlene B. TITLE Deaf Infants' Coordination of Attention to Persons and Objects. PUB DATE Mar 93 NOTE 12p.; Poster presented at the Society for Research in Child Development (New Orleans, LA, March 25-28, 1993). PUB TYPE Speeches/Conference Papers (150) Reports Research/Technical (143) EDRS PRICE MF01/PC01 Plus Postage. DESCRIPTORS *Attention; Attention Control; Child Development; *Deafness; *Infant Behavior; Infants;...»

«Constructing Summary Statistics for Approximate Bayesian Computation: Semi-automatic ABC arXiv:1004.1112v2 [stat.ME] 13 Apr 2011 Paul Fearnhead and Dennis Prangle Department of Mathematics and Statistics, Lancaster University, UK Abstract Many modern statistical applications involve inference for complex stochastic models, where it is easy to simulate from the models, but impossible to calculate likelihoods. Approximate Bayesian computation (ABC) is a method of inference for such models. It...»

«FREUND, FEIND UND VERRAT Mediologie Band 12 Eine Schriftenreihe des Kulturwissenschaftlichen Forschungskollegs »Medien und kulturelle Kommunikation« Herausgegeben von Ludwig Jäger FREUND, FEIND & VERRAT DAS POLITISCHE FELD DER MEDIEN Herausgegeben von Cornelia Epping-Jäger, Thorsten Hahn, und Erhard Schüttpelz DuMont Diese Publikation ist im Sonderforschungsbereich/Kulturwissenschaftlichen Forschungskolleg 427 »Medien und kulturelle Kommunikation«, Köln, entstanden und wurde auf seine...»

«UNITED STATES DEPARTMENT OF EDUCATION OFFICE OF INSPECTOR GENERAL Evaluation and Inspection Services Control Number ED-OIG/X13J0003 May 24, 2010 Dr. Sylvia Manning President The Higher Learning Commission 30 North LaSalle Street, Suite 2400 Chicago, Illinois 60602-2504 Dear Dr. Manning: This final management information report entitled, Review of The Higher Learning Commission of the North Central Association of Colleges and Schools’ Standards for Program Length, presents the results of our...»

«International Journal of Network Security & Its Applications (IJNSA), Vol.5, No.2, March 2013 PRIVACY PRESERVING DATA MINING BY USING IMPLICIT FUNCTION THEOREM Pasupuleti Rajesh1 and Gugulothu Narsimha2 Department of Computer Science and Engineering, VVIT College, Guntur, India rajesh.pleti@gmail.com Department of Computer Science and Engineering, JNTUH University, Hyderabad, India narsimha06@gmail.com ABSTRACT Data mining has made broad significant multidisciplinary field used in vast...»

«Downloading and distribution via your company’s intranet of the following article in accordance with the terms and conditions hereinafter set forth is authorized by SAS Institute Inc. Each article must be distributed in complete form with all associated copyright, trademark, and other proprietary notices. No additional copyright, trademark, or other proprietary notices may be attached to or included with any article.THE ARTICLE CONTAINED HEREIN IS PROVIDED BY SAS INSTITUTE INC. “AS IS”...»

«Visualisation and Instructional Design John Sweller School of Education University of New South Wales Sydney NSW 2052 Australia j.sweller@unsw.edu.au University of New South Wales Abstract Human cognitive architecture includes a working memory of limited capacity and duration with partially separate visual and auditory channels, and an effectively infinite long-term memory holding many schemas that can vary in their degree of automation. These cognitive structures have evolved to handle...»

«Danish – German Research Papers Department for Border Region Studies (IFG) International Institute of Management (IIM) Peer-reviewed Flensburg / Sønderborg ISSN 1868-8160 Joint Research Paper Series: International Institute of Management and Department of Border Region Studies The Department of Border Region Studies at the University of Southern Denmark and the International Institute of Management at the University of Flensburg have established a joint research paper series to further...»

«THE NATURE CRIME: CONTINUITY CHANGE OF AND Explaining Regional and Urban Variation in Crime: A Review of Research by Graham C. Ousey Beginning with the moral statisticians Guerry and Quetelet and conA tinuing to the present, criminologists have repeatedly shown that seriB ous crime rates vary across geographic units. The most prominent framework for explaining this variation is the macrosocial perspecS tive, which asserts that the crime rate is a reflection of social organiT zation. In this...»

«COMPUTER-AIDED CRITIQUING SYSTEMS Lessons Learned and New Research Directions YEONJOO OH, MARK D GROSS CoDe Lab, School of Architecture, Carnegie Mellon University Email addresses: yeonjoo@cmu.edu, mdgross@cmu.edu AND ELLEN YI-LUEN DO College of Architecture and College of Computing, Georgia Institute of Technology Email address: ellendo@cc.gatech.edu Abstract. A critiquing system helps designers improve their design artifacts by providing feedback. Computer-aided critiquing systems have been...»

«Religion und Demokratie Muslimische und christliche Perspektiven Dokumentation zu einem interreligiösen Besuchsund Dialogprogramm mit Gästen aus Indonesien 106 Schriftenreihe Gerechtigkeit und Frieden Schriftenreihe Gerechtigkeit und Frieden Published by the German Commission for Justice and Peace Herausgeber: Deutsche Kommission Justitia et Pax Editor: Gertrud Casel Redaktion: Gertrud Casel _ _ Religion und Demokratie. Muslimische und christliche Perspektiven. Dokumentation zu einem...»

<<  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.