1
$\begingroup$

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 $\mathbb{S}^2$, as this will tell me how many exposed faces of a simplicial $3$-complex there are among a certain subset of $n$-points in $\mathbb{E}^3$. 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 $\mathbb{S}^2$.

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 $(d-1)\frac{\pi}{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 $\mathbb{S}^2$".

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 $b_{d}$ denote the total number of vertices of this polygon and the number of those vertices that have degree $d$ in $G$, respsectively. Clearly, $b = b_{2} + b_{3} + b_{4} + b_{5}$. The internal angle of $C$ at a vertex of degree $d$ is at least $(d-1)\frac{\pi}{3}$, and the sum of these angles is $(b-2)\pi$. Hence, $b_{2} + 2b_{3} + 3b_{4} + 4b_{5} \leq 3b-6$.

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 $P \subseteq \mathbb{S}^2$ of $n$ points with minimum distance $\frac{\pi}{3}$, and connect two elements of $P$ by a great arc if and only if their distance is exactly $\frac{\pi}{3}$.


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

Where does the condition come from in $\mathbb{E}^2$ that, "the internal angle of $C$ at a vertex of degree $d$ is at least $(d-1)\frac{\pi}{3}$". Can a similar condition be generalized to my case on $\mathbb{S}^2$?

$\endgroup$
4
  • 2
    $\begingroup$ @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"? $\endgroup$ May 16, 2012 at 0:15
  • $\begingroup$ @Joseph O'Rourke: Thank you for the suggestion, I have added more context. Let me know if it is still unclear. $\endgroup$ May 16, 2012 at 0:50
  • $\begingroup$ Why is there no $b_6$? 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? $\endgroup$
    – Will Jagy
    May 16, 2012 at 0:56
  • $\begingroup$ @Will Jagy: According to Pach and Agarwal, there is no $b_{6}$, 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 $\mathbb{S}^2$, the graph is not required to be in only one hemisphere, but I know that it does not partition $\mathbb{S}^2$ into equal size cells. The edges of the arcs are great circles of edge length $\frac{pi}{3}$, by $s=r \theta$. $\endgroup$ May 16, 2012 at 1:22

1 Answer 1

1
$\begingroup$

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 $\pi/3$. If $C$ is adjacent to $X_1,X_2,\dots,X_d$, where the $X_i$ are taken in, say, clockwise order with respect to $C$, then each angle $X_iCX_{i+1}$ is at least $\pi/3$, so the total angle at $C$ is at least $(d-1)(\pi/3)$.

$\endgroup$
3
  • $\begingroup$ @GerryMyerson: Thank you for this response. I was able to generalize to $\mathbb{S}^2$ and prove the last lemma which was holding me back from a result I have been working on for a week. $\endgroup$ May 16, 2012 at 6:05
  • $\begingroup$ It seems like an utterly trivial problem after your response though! $\endgroup$ May 16, 2012 at 6:11
  • $\begingroup$ Utterly trivial is what I do best. $\endgroup$ May 16, 2012 at 12:41

Your Answer

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

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