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$ Commented 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$ Commented 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
    Commented 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$ Commented 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$ Commented May 16, 2012 at 6:05
  • $\begingroup$ It seems like an utterly trivial problem after your response though! $\endgroup$ Commented May 16, 2012 at 6:11
  • $\begingroup$ Utterly trivial is what I do best. $\endgroup$ Commented May 16, 2012 at 12:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .