Interpreting a problem in combinatorial geometry Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Number of line segments intersecting diagonals are divided into in a convex polygonLazy caterer's sequence, cutting pizza into most pieces with n straight cuts. Graph theory proof.Trying to understand formula for counting regions of hyperplane arrangements in $mathbbR^2$n lines cut a plane into at least (n+1)(n+2)n/3 regions.no. of regions a plane is divided into by $n$ lines in general positionAnother olympiad question related to Extremal Principle (regarding geometry problem)In how many parts is a plane cut by n lines, or a space cut by n planes?Question about how we count the number of ways to do a task.Combinatorics problem with geometryCounting regions outside a convex hull
Do square wave exist?
What does this Jacques Hadamard quote mean?
Most bit efficient text communication method?
What are the out-of-universe reasons for the references to Toby Maguire-era Spider-Man in ITSV
How can I use the Python library networkx from Mathematica?
Can a party unilaterally change candidates in preparation for a General election?
When a candle burns, why does the top of wick glow if bottom of flame is hottest?
How to tell that you are a giant?
Does classifying an integer as a discrete log require it be part of a multiplicative group?
Why didn't Eitri join the fight?
How does the math work when buying airline miles?
Is it common practice to audition new musicians 1-2-1 before rehearsing with the entire band?
Extracting terms with certain heads in a function
Integration Help
Do wooden building fires get hotter than 600°C?
Closed form of recurrent arithmetic series summation
Is "Reachable Object" really an NP-complete problem?
What is homebrew?
What causes the direction of lightning flashes?
How to Make a Beautiful Stacked 3D Plot
Wu formula for manifolds with boundary
Withdrew £2800, but only £2000 shows as withdrawn on online banking; what are my obligations?
Is there such thing as an Availability Group failover trigger?
First console to have temporary backward compatibility
Interpreting a problem in combinatorial geometry
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Number of line segments intersecting diagonals are divided into in a convex polygonLazy caterer's sequence, cutting pizza into most pieces with n straight cuts. Graph theory proof.Trying to understand formula for counting regions of hyperplane arrangements in $mathbbR^2$n lines cut a plane into at least (n+1)(n+2)n/3 regions.no. of regions a plane is divided into by $n$ lines in general positionAnother olympiad question related to Extremal Principle (regarding geometry problem)In how many parts is a plane cut by n lines, or a space cut by n planes?Question about how we count the number of ways to do a task.Combinatorics problem with geometryCounting regions outside a convex hull
$begingroup$
Problem: Let $L$ be a set of $n$ lines in the plane in general position, that is, no three of them containing the same point. The lines of $L$ cut the plane into $k$ regions. Prove by induction on $n$ that this subdivision of the plane has $binomn2$ vertices, $n^2$ edges, and $binomn2 + n + 1$ cells.
I don't need help solving this problem, I just need help interpreting it. What does it mean that the plane is cut into $k$ regions? I thought that the number of regions was determined by $n$. Also, what's the point of the $k$ if we're not proving anything about it?
Finally, what is meant by cells? Also, are edges the finite segments between intersections?
combinatorics euclidean-geometry
asked Apr 1 at 13:15
WesleyWesley
619613
$endgroup$
add a comment |
$begingroup$
Problem: Let $L$ be a set of $n$ lines in the plane in general position, that is, no three of them containing the same point. The lines of $L$ cut the plane into $k$ regions. Prove by induction on $n$ that this subdivision of the plane has $binomn2$ vertices, $n^2$ edges, and $binomn2 + n + 1$ cells.
I don't need help solving this problem, I just need help interpreting it. What does it mean that the plane is cut into $k$ regions? I thought that the number of regions was determined by $n$. Also, what's the point of the $k$ if we're not proving anything about it?
Finally, what is meant by cells? Also, are edges the finite segments between intersections?
combinatorics euclidean-geometry
asked Apr 1 at 13:15
WesleyWesley
619613
$endgroup$
3
$begingroup$
I agree the statement is not as clear as it could be. For one thing, it explains that "general position" means no three lines through the same point, but it doesn't mention that no two lines can be parallel (which I believe is also intended by "general position"). And they could have said "some number of" instead of $k$, so the use of that symbol was unnecessary.
$endgroup$
– David K
Apr 1 at 13:29
add a comment |
$begingroup$
Problem: Let $L$ be a set of $n$ lines in the plane in general position, that is, no three of them containing the same point. The lines of $L$ cut the plane into $k$ regions. Prove by induction on $n$ that this subdivision of the plane has $binomn2$ vertices, $n^2$ edges, and $binomn2 + n + 1$ cells.
I don't need help solving this problem, I just need help interpreting it. What does it mean that the plane is cut into $k$ regions? I thought that the number of regions was determined by $n$. Also, what's the point of the $k$ if we're not proving anything about it?
Finally, what is meant by cells? Also, are edges the finite segments between intersections?
combinatorics euclidean-geometry
asked Apr 1 at 13:15
WesleyWesley
619613
$endgroup$
Problem: Let $L$ be a set of $n$ lines in the plane in general position, that is, no three of them containing the same point. The lines of $L$ cut the plane into $k$ regions. Prove by induction on $n$ that this subdivision of the plane has $binomn2$ vertices, $n^2$ edges, and $binomn2 + n + 1$ cells.
I don't need help solving this problem, I just need help interpreting it. What does it mean that the plane is cut into $k$ regions? I thought that the number of regions was determined by $n$. Also, what's the point of the $k$ if we're not proving anything about it?
Finally, what is meant by cells? Also, are edges the finite segments between intersections?
combinatorics euclidean-geometry
combinatorics euclidean-geometry
asked Apr 1 at 13:15
WesleyWesley
619613
asked Apr 1 at 13:15
WesleyWesley
619613
asked Apr 1 at 13:15
WesleyWesley
619613
asked Apr 1 at 13:15
WesleyWesley
619613
asked Apr 1 at 13:15
WesleyWesley
619613
619613
3
$begingroup$
I agree the statement is not as clear as it could be. For one thing, it explains that "general position" means no three lines through the same point, but it doesn't mention that no two lines can be parallel (which I believe is also intended by "general position"). And they could have said "some number of" instead of $k$, so the use of that symbol was unnecessary.
$endgroup$
– David K
Apr 1 at 13:29
add a comment |
3
$begingroup$
I agree the statement is not as clear as it could be. For one thing, it explains that "general position" means no three lines through the same point, but it doesn't mention that no two lines can be parallel (which I believe is also intended by "general position"). And they could have said "some number of" instead of $k$, so the use of that symbol was unnecessary.
$endgroup$
– David K
Apr 1 at 13:29
3
3
$begingroup$
I agree the statement is not as clear as it could be. For one thing, it explains that "general position" means no three lines through the same point, but it doesn't mention that no two lines can be parallel (which I believe is also intended by "general position"). And they could have said "some number of" instead of $k$, so the use of that symbol was unnecessary.
$endgroup$
– David K
Apr 1 at 13:29
$begingroup$
I agree the statement is not as clear as it could be. For one thing, it explains that "general position" means no three lines through the same point, but it doesn't mention that no two lines can be parallel (which I believe is also intended by "general position"). And they could have said "some number of" instead of $k$, so the use of that symbol was unnecessary.
$endgroup$
– David K
Apr 1 at 13:29
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I tried the case for $n=3$ and I think i found the correct interpretation, but you should do it yourself to confirm. It seems that they do not allow for parallel lines, in which case you are right that the $k$ in "$k$ regions" is not relevant.
"Vertices" is clear: a vertex is a point where a pair of lines intersect
"Edges" are any piece of line: a finite line segment between vertices, an infinite ray emanating from a vertex, or a whole line (in the case of $n=1$)
"Cells" means any face created by the lines. In other words, a region of the plane is a cell if you can draw a continuous path between any 2 points in the cell without crossing a line
answered Apr 1 at 13:28
NazimJNazimJ
890110
$endgroup$
add a comment |
$begingroup$
For the statement to be correct, no two lines may be parallel. The symbol $k$ has no significance whatsoever, and might as well be omitted; the question would have been clearer if it said
The lines of $L$ cut the plane into some number of regions.
The question is also poorly phrased as it does not specify what the words "vertices", "edges", "regions" and "cells" mean. Judging from the given formulas, my best guess is the following:
A vertex is a point of intersection of two lines. Denote the set of vertices by $V$:
$$V:=lcap m: l,min L.$$
The vertices partition the lines into segments; these are the edges. Note that some are bounded and some are unbounded. More precisely, the set of edges is the set of connected components of $(bigcup L)-V$.
Similarly, omitting the lines from the plane leaves a number of regions, and again some are bounded and some are unbounded. The cells are the bounded regions. More precisely, the set of regions is the set of connected components of $P-bigcup L$, where $P$ denotes the plane, and the set of cells is the subset of bounded connected components of $P-bigcup L$.
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3170600%2finterpreting-a-problem-in-combinatorial-geometry%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I tried the case for $n=3$ and I think i found the correct interpretation, but you should do it yourself to confirm. It seems that they do not allow for parallel lines, in which case you are right that the $k$ in "$k$ regions" is not relevant.
"Vertices" is clear: a vertex is a point where a pair of lines intersect
"Edges" are any piece of line: a finite line segment between vertices, an infinite ray emanating from a vertex, or a whole line (in the case of $n=1$)
"Cells" means any face created by the lines. In other words, a region of the plane is a cell if you can draw a continuous path between any 2 points in the cell without crossing a line
answered Apr 1 at 13:28
NazimJNazimJ
890110
$endgroup$
add a comment |
$begingroup$
I tried the case for $n=3$ and I think i found the correct interpretation, but you should do it yourself to confirm. It seems that they do not allow for parallel lines, in which case you are right that the $k$ in "$k$ regions" is not relevant.
"Vertices" is clear: a vertex is a point where a pair of lines intersect
"Edges" are any piece of line: a finite line segment between vertices, an infinite ray emanating from a vertex, or a whole line (in the case of $n=1$)
"Cells" means any face created by the lines. In other words, a region of the plane is a cell if you can draw a continuous path between any 2 points in the cell without crossing a line
answered Apr 1 at 13:28
NazimJNazimJ
890110
$endgroup$
add a comment |
$begingroup$
I tried the case for $n=3$ and I think i found the correct interpretation, but you should do it yourself to confirm. It seems that they do not allow for parallel lines, in which case you are right that the $k$ in "$k$ regions" is not relevant.
"Vertices" is clear: a vertex is a point where a pair of lines intersect
"Edges" are any piece of line: a finite line segment between vertices, an infinite ray emanating from a vertex, or a whole line (in the case of $n=1$)
"Cells" means any face created by the lines. In other words, a region of the plane is a cell if you can draw a continuous path between any 2 points in the cell without crossing a line
answered Apr 1 at 13:28
NazimJNazimJ
890110
$endgroup$
I tried the case for $n=3$ and I think i found the correct interpretation, but you should do it yourself to confirm. It seems that they do not allow for parallel lines, in which case you are right that the $k$ in "$k$ regions" is not relevant.
"Vertices" is clear: a vertex is a point where a pair of lines intersect
"Edges" are any piece of line: a finite line segment between vertices, an infinite ray emanating from a vertex, or a whole line (in the case of $n=1$)
"Cells" means any face created by the lines. In other words, a region of the plane is a cell if you can draw a continuous path between any 2 points in the cell without crossing a line
answered Apr 1 at 13:28
NazimJNazimJ
890110
answered Apr 1 at 13:28
NazimJNazimJ
890110
answered Apr 1 at 13:28
NazimJNazimJ
890110
answered Apr 1 at 13:28
NazimJNazimJ
890110
890110
add a comment |
add a comment |
$begingroup$
For the statement to be correct, no two lines may be parallel. The symbol $k$ has no significance whatsoever, and might as well be omitted; the question would have been clearer if it said
The lines of $L$ cut the plane into some number of regions.
The question is also poorly phrased as it does not specify what the words "vertices", "edges", "regions" and "cells" mean. Judging from the given formulas, my best guess is the following:
A vertex is a point of intersection of two lines. Denote the set of vertices by $V$:
$$V:=lcap m: l,min L.$$
The vertices partition the lines into segments; these are the edges. Note that some are bounded and some are unbounded. More precisely, the set of edges is the set of connected components of $(bigcup L)-V$.
Similarly, omitting the lines from the plane leaves a number of regions, and again some are bounded and some are unbounded. The cells are the bounded regions. More precisely, the set of regions is the set of connected components of $P-bigcup L$, where $P$ denotes the plane, and the set of cells is the subset of bounded connected components of $P-bigcup L$.
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
$endgroup$
add a comment |
$begingroup$
For the statement to be correct, no two lines may be parallel. The symbol $k$ has no significance whatsoever, and might as well be omitted; the question would have been clearer if it said
The lines of $L$ cut the plane into some number of regions.
The question is also poorly phrased as it does not specify what the words "vertices", "edges", "regions" and "cells" mean. Judging from the given formulas, my best guess is the following:
A vertex is a point of intersection of two lines. Denote the set of vertices by $V$:
$$V:=lcap m: l,min L.$$
The vertices partition the lines into segments; these are the edges. Note that some are bounded and some are unbounded. More precisely, the set of edges is the set of connected components of $(bigcup L)-V$.
Similarly, omitting the lines from the plane leaves a number of regions, and again some are bounded and some are unbounded. The cells are the bounded regions. More precisely, the set of regions is the set of connected components of $P-bigcup L$, where $P$ denotes the plane, and the set of cells is the subset of bounded connected components of $P-bigcup L$.
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
$endgroup$
add a comment |
$begingroup$
For the statement to be correct, no two lines may be parallel. The symbol $k$ has no significance whatsoever, and might as well be omitted; the question would have been clearer if it said
The lines of $L$ cut the plane into some number of regions.
The question is also poorly phrased as it does not specify what the words "vertices", "edges", "regions" and "cells" mean. Judging from the given formulas, my best guess is the following:
A vertex is a point of intersection of two lines. Denote the set of vertices by $V$:
$$V:=lcap m: l,min L.$$
The vertices partition the lines into segments; these are the edges. Note that some are bounded and some are unbounded. More precisely, the set of edges is the set of connected components of $(bigcup L)-V$.
Similarly, omitting the lines from the plane leaves a number of regions, and again some are bounded and some are unbounded. The cells are the bounded regions. More precisely, the set of regions is the set of connected components of $P-bigcup L$, where $P$ denotes the plane, and the set of cells is the subset of bounded connected components of $P-bigcup L$.
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
$endgroup$
For the statement to be correct, no two lines may be parallel. The symbol $k$ has no significance whatsoever, and might as well be omitted; the question would have been clearer if it said
The lines of $L$ cut the plane into some number of regions.
The question is also poorly phrased as it does not specify what the words "vertices", "edges", "regions" and "cells" mean. Judging from the given formulas, my best guess is the following:
A vertex is a point of intersection of two lines. Denote the set of vertices by $V$:
$$V:=lcap m: l,min L.$$
The vertices partition the lines into segments; these are the edges. Note that some are bounded and some are unbounded. More precisely, the set of edges is the set of connected components of $(bigcup L)-V$.
Similarly, omitting the lines from the plane leaves a number of regions, and again some are bounded and some are unbounded. The cells are the bounded regions. More precisely, the set of regions is the set of connected components of $P-bigcup L$, where $P$ denotes the plane, and the set of cells is the subset of bounded connected components of $P-bigcup L$.
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
answered Apr 1 at 13:47
ServaesServaes
30.7k342101
30.7k342101
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3170600%2finterpreting-a-problem-in-combinatorial-geometry%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
I agree the statement is not as clear as it could be. For one thing, it explains that "general position" means no three lines through the same point, but it doesn't mention that no two lines can be parallel (which I believe is also intended by "general position"). And they could have said "some number of" instead of $k$, so the use of that symbol was unnecessary.
$endgroup$
– David K
Apr 1 at 13:29