Skip to main content
Added comments to address the comments.
Source Link
Samuel Reid
  • 1.4k
  • 11
  • 23

"Obvious" claim in combinatorial geometry about Generalizing the internal angle of a graph in $\mathbb{E}^2$ to $\mathbb{S}^2$

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$?

"Obvious" claim in combinatorial geometry about the internal angle of a graph

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$"

Generalizing the internal angle of a graph in $\mathbb{E}^2$ to $\mathbb{S}^2$

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$?

added 920 characters in body
Source Link
Samuel Reid
  • 1.4k
  • 11
  • 23

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$"

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.

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$"

Source Link
Samuel Reid
  • 1.4k
  • 11
  • 23

"Obvious" claim in combinatorial geometry about the internal angle of a graph

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.