1

I am currently working on research involving packing problems and am finding myself needing the tools from Combinatorial Geometry (in particular, I've been reading Pach and Agarwal's book on the subject) and I am in the dark on what I think should be a very simple point. I apologize if the question is too elementary for MO.

For reasons I won't get into, I am needing to give a bound for the number of spherical 2-simplexes which can occur among n-points in S2, as this will tell me how many exposed faces of a simplicial 3-complex there are among a certain subset of n-points in E3. I am at a point in a Lemma where I am needing to generalize the following claim about graphs in the plane, to simplicial 2-complexes (graphs) in S2.

I cite from Pach and Agarwal's Combinatorial Geometry: "The internal angle of a simple closed polygon C which bounds a graph G at a vertex of degree d is at least (d1)π3."

Does anyone know a proof of this fact, or have a simple explanation of it so that I can have a hope of generalizing it to "the internal angle of a simple closed spherical polygon which bounds a simplicial 2-complex at a vertex of degree d is at least [something] in S2".

Thank you, I appreciate any responses.

EDIT: Due to Joseph O'Rourke's comment I will quote a larger passage from the book so that there is more context.

The properties of a graph G are being discussed and the following is mentioned:

The outer face of G is bounded by a simple closed polygon C. Let b and bd denote the total number of vertices of this polygon and the number of those vertices that have degree d in G, respsectively. Clearly, b=b2+b3+b4+b5. The internal angle of C at a vertex of degree d is at least (d1)π3, and the sum of these angles is (b2)π. Hence, b2+2b3+3b4+4b53b6.

My interpretation of this is that we look at the boundary of our graph G, and note that it is a closed polygon. The angles of this polygon at a particular vertex (namely, one of degree d in the graph G) is the "the internal angle of C at a vertex of degree d"

EDIT 2: I apologize, there seems to be more background that I need to mention in order for this to make sense. As mentioned in my comment directed towards Will Jagy, the following condition is to hold for our graph G in the plane. Consider a set P of n points with minimum distance 1, and connect two elements of P by a segment if and only if their distance is exactly 1. Thus, we obtain a graph G embedded in the plane. For my case, I want to consider a set PS2 of n points with minimum distance π3, and connect two elements of P by a great arc if and only if their distance is exactly π3.


Hopefully that was the last edit, but I will reiterate exactly what my question is.

Where does the condition come from in E2 that, "the internal angle of C at a vertex of degree d is at least (d1)π3". Can a similar condition be generalized to my case on S2?

CC BY-SA 3.0
4
  • 2
    @Samuel: I don't have the P&A book with me, and just from the words you quoted I cannot figure out what it means. Perhaps others may have the same difficulty. What does it mean for a "polygon to bound a graph at a vertex"? May 16, 2012 at 0:15
  • @Joseph O'Rourke: Thank you for the suggestion, I have added more context. Let me know if it is still unclear. May 16, 2012 at 0:50
  • Why is there no b6? I can understand being bounded by a closed polygon, essentially if we demand no isolated vertices and none of valence 1. Is a graph required to be in a hemisphere or some such? Are the edges arcs of great circles?
    – Will Jagy
    May 16, 2012 at 0:56
  • @Will Jagy: According to Pach and Agarwal, there is no b6, maybe this has to do with the restriction which is forgot to mention which is that the edge length of the graph must be 1 and no two vertices of the graph (connected by an edge or not) can be closer than 1 unit distance away. For my case I am looking at in S2, the graph is not required to be in only one hemisphere, but I know that it does not partition S2 into equal size cells. The edges of the arcs are great circles of edge length pi3, by s=rθ. May 16, 2012 at 1:22

1 Answer 1

1

If vertex C is adjacent to vertices X and Y, then the distances CX and CY are 1, and the distance XY is at least 1, so the angle XCY is at least π/3. If C is adjacent to X1,X2,,Xd, where the Xi are taken in, say, clockwise order with respect to C, then each angle XiCXi+1 is at least π/3, so the total angle at C is at least (d1)(π/3).

CC BY-SA 3.0
3
  • @GerryMyerson: Thank you for this response. I was able to generalize to S2 and prove the last lemma which was holding me back from a result I have been working on for a week. May 16, 2012 at 6:05
  • It seems like an utterly trivial problem after your response though! May 16, 2012 at 6:11
  • Utterly trivial is what I do best. May 16, 2012 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.