Minimum number of distinct distances in a planeLower bound for a set of distances between pairs of points in a planePairs of points exactly $1$ unit apart in the planeEmbedding finite (discrete) metric spaces to Eulidean space as isometrically as possibleNumber of possible combinations of the Enigma machine plugboardChoosing k pairs l distance apart from n numbersNearly-unit-distance graph (UDG) densityCombinatoral Geometry with DistancesMinimum number of points to intersect any circle in the regionFinding the number of distinct extrema of polynomial.Set of Integers, find expectation of twin pairs (defined in description)
Unable to disable Microsoft Store in domain environment
Language involving irrational number is not a CFL
Determining multivariate least squares with constraint
What happens if I try to grapple mirror image?
Is there a RAID 0 Equivalent for RAM?
Are inadvertent environmental catastrophes also examples of natural selection?
Can I cause damage to electrical appliances by unplugging them when they are turned on?
Do you waste sorcery points if you try to apply metamagic to a spell from a scroll but fail to cast it?
Has the laser at Magurele, Romania reached a tenth of the Sun's power?
If Captain Marvel (MCU) were to have a child with a human male, would the child be human or Kree?
Should I assume I have passed probation?
The Digit Triangles
Why would five hundred and five be same as one?
Deciphering cause of death?
How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?
Would a primitive species be able to learn English from reading books alone?
Anime with legendary swords made from talismans and a man who could change them with a shattered body
Why do Radio Buttons not fill the entire outer circle?
If the only attacker is removed from combat, is a creature still counted as having attacked this turn?
Why can't the Brexit deadlock in the UK parliament be solved with a plurality vote?
Why does the Persian emissary display a string of crowned skulls?
What is the meaning of "You've never met a graph you didn't like?"
What is this high flying aircraft over Pennsylvania?
Giving feedback to someone without sounding prejudiced
Minimum number of distinct distances in a plane
Lower bound for a set of distances between pairs of points in a planePairs of points exactly $1$ unit apart in the planeEmbedding finite (discrete) metric spaces to Eulidean space as isometrically as possibleNumber of possible combinations of the Enigma machine plugboardChoosing k pairs l distance apart from n numbersNearly-unit-distance graph (UDG) densityCombinatoral Geometry with DistancesMinimum number of points to intersect any circle in the regionFinding the number of distinct extrema of polynomial.Set of Integers, find expectation of twin pairs (defined in description)
$begingroup$
Let $U(n)$ denote the maximum possible number of pairs of points in an $n$-point subset of $Bbb R^2$ that are unit distance apart.
Let $g(n)$ be the minimum number of distinct distances determined by $n$ points in $Bbb R^2$, that is:
$$g(n)=textmin_Pleft|textdist(x,y)mid x,yin Pright|.$$
My textbook says "Clearly $g(n)geq nchoose 2 / U(n)$". Why is this so? I have no idea how to even show that this is reasonable. My first thought is that there are clearly $nchoose 2$ pairs and if $U(n)=nchoose 2$, i.e. they are all unit distance apart, then indeed $g(n)=1$. Otherwise as $U(n)$ gets smaller, $g(n)$ should get bigger, which seems okay intuitively. But I don't see how to show this
Actually, a thought after typing this out: Perhaps they are thinking about taking all pairs, and breaking them up into $U(n)$ sized groups, of which would would have $nchoose 2/U(n)$, and one cannot do better than this.
combinatorics discrete-geometry
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
asked Apr 2 '18 at 15:42
user547222user547222
155
$endgroup$
add a comment |
$begingroup$
Let $U(n)$ denote the maximum possible number of pairs of points in an $n$-point subset of $Bbb R^2$ that are unit distance apart.
Let $g(n)$ be the minimum number of distinct distances determined by $n$ points in $Bbb R^2$, that is:
$$g(n)=textmin_Pleft|textdist(x,y)mid x,yin Pright|.$$
My textbook says "Clearly $g(n)geq nchoose 2 / U(n)$". Why is this so? I have no idea how to even show that this is reasonable. My first thought is that there are clearly $nchoose 2$ pairs and if $U(n)=nchoose 2$, i.e. they are all unit distance apart, then indeed $g(n)=1$. Otherwise as $U(n)$ gets smaller, $g(n)$ should get bigger, which seems okay intuitively. But I don't see how to show this
Actually, a thought after typing this out: Perhaps they are thinking about taking all pairs, and breaking them up into $U(n)$ sized groups, of which would would have $nchoose 2/U(n)$, and one cannot do better than this.
combinatorics discrete-geometry
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
asked Apr 2 '18 at 15:42
user547222user547222
155
$endgroup$
1
$begingroup$
How does $U(n)$ depend on $n$?
$endgroup$
– Fimpellizieri
Apr 2 '18 at 15:45
$begingroup$
@Fimpellizieri fixed
$endgroup$
– user547222
Apr 2 '18 at 15:46
$begingroup$
Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
$endgroup$
– saulspatz
Apr 2 '18 at 15:51
$begingroup$
This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
$endgroup$
– Hagen von Eitzen
Apr 2 '18 at 15:53
add a comment |
$begingroup$
Let $U(n)$ denote the maximum possible number of pairs of points in an $n$-point subset of $Bbb R^2$ that are unit distance apart.
Let $g(n)$ be the minimum number of distinct distances determined by $n$ points in $Bbb R^2$, that is:
$$g(n)=textmin_Pleft|textdist(x,y)mid x,yin Pright|.$$
My textbook says "Clearly $g(n)geq nchoose 2 / U(n)$". Why is this so? I have no idea how to even show that this is reasonable. My first thought is that there are clearly $nchoose 2$ pairs and if $U(n)=nchoose 2$, i.e. they are all unit distance apart, then indeed $g(n)=1$. Otherwise as $U(n)$ gets smaller, $g(n)$ should get bigger, which seems okay intuitively. But I don't see how to show this
Actually, a thought after typing this out: Perhaps they are thinking about taking all pairs, and breaking them up into $U(n)$ sized groups, of which would would have $nchoose 2/U(n)$, and one cannot do better than this.
combinatorics discrete-geometry
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
asked Apr 2 '18 at 15:42
user547222user547222
155
$endgroup$
Let $U(n)$ denote the maximum possible number of pairs of points in an $n$-point subset of $Bbb R^2$ that are unit distance apart.
Let $g(n)$ be the minimum number of distinct distances determined by $n$ points in $Bbb R^2$, that is:
$$g(n)=textmin_Pleft|textdist(x,y)mid x,yin Pright|.$$
My textbook says "Clearly $g(n)geq nchoose 2 / U(n)$". Why is this so? I have no idea how to even show that this is reasonable. My first thought is that there are clearly $nchoose 2$ pairs and if $U(n)=nchoose 2$, i.e. they are all unit distance apart, then indeed $g(n)=1$. Otherwise as $U(n)$ gets smaller, $g(n)$ should get bigger, which seems okay intuitively. But I don't see how to show this
Actually, a thought after typing this out: Perhaps they are thinking about taking all pairs, and breaking them up into $U(n)$ sized groups, of which would would have $nchoose 2/U(n)$, and one cannot do better than this.
combinatorics discrete-geometry
combinatorics discrete-geometry
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
asked Apr 2 '18 at 15:42
user547222user547222
155
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
asked Apr 2 '18 at 15:42
user547222user547222
155
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
edited Mar 14 at 5:44
Martin Sleziak
44.9k10121274
44.9k10121274
asked Apr 2 '18 at 15:42
user547222user547222
155
asked Apr 2 '18 at 15:42
user547222user547222
155
asked Apr 2 '18 at 15:42
user547222user547222
155
155
1
$begingroup$
How does $U(n)$ depend on $n$?
$endgroup$
– Fimpellizieri
Apr 2 '18 at 15:45
$begingroup$
@Fimpellizieri fixed
$endgroup$
– user547222
Apr 2 '18 at 15:46
$begingroup$
Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
$endgroup$
– saulspatz
Apr 2 '18 at 15:51
$begingroup$
This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
$endgroup$
– Hagen von Eitzen
Apr 2 '18 at 15:53
add a comment |
1
$begingroup$
How does $U(n)$ depend on $n$?
$endgroup$
– Fimpellizieri
Apr 2 '18 at 15:45
$begingroup$
@Fimpellizieri fixed
$endgroup$
– user547222
Apr 2 '18 at 15:46
$begingroup$
Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
$endgroup$
– saulspatz
Apr 2 '18 at 15:51
$begingroup$
This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
$endgroup$
– Hagen von Eitzen
Apr 2 '18 at 15:53
1
1
$begingroup$
How does $U(n)$ depend on $n$?
$endgroup$
– Fimpellizieri
Apr 2 '18 at 15:45
$begingroup$
How does $U(n)$ depend on $n$?
$endgroup$
– Fimpellizieri
Apr 2 '18 at 15:45
$begingroup$
@Fimpellizieri fixed
$endgroup$
– user547222
Apr 2 '18 at 15:46
$begingroup$
@Fimpellizieri fixed
$endgroup$
– user547222
Apr 2 '18 at 15:46
$begingroup$
Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
$endgroup$
– saulspatz
Apr 2 '18 at 15:51
$begingroup$
Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
$endgroup$
– saulspatz
Apr 2 '18 at 15:51
$begingroup$
This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
$endgroup$
– Hagen von Eitzen
Apr 2 '18 at 15:53
$begingroup$
This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
$endgroup$
– Hagen von Eitzen
Apr 2 '18 at 15:53
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Given an $n$-set $Ssubset mathbb R^2$, consider
$$mathscr S = (x,y),.$$
Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by
$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$
The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.
Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.
With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
$endgroup$
1
$begingroup$
Really neat, thanks!
$endgroup$
– user547222
Apr 2 '18 at 16:18
$begingroup$
You're welcome! Glad to help.
$endgroup$
– Fimpellizieri
Apr 2 '18 at 16:19
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
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%2f2718927%2fminimum-number-of-distinct-distances-in-a-plane%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Given an $n$-set $Ssubset mathbb R^2$, consider
$$mathscr S = (x,y),.$$
Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by
$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$
The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.
Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.
With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
$endgroup$
1
$begingroup$
Really neat, thanks!
$endgroup$
– user547222
Apr 2 '18 at 16:18
$begingroup$
You're welcome! Glad to help.
$endgroup$
– Fimpellizieri
Apr 2 '18 at 16:19
add a comment |
$begingroup$
Given an $n$-set $Ssubset mathbb R^2$, consider
$$mathscr S = (x,y),.$$
Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by
$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$
The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.
Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.
With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
$endgroup$
1
$begingroup$
Really neat, thanks!
$endgroup$
– user547222
Apr 2 '18 at 16:18
$begingroup$
You're welcome! Glad to help.
$endgroup$
– Fimpellizieri
Apr 2 '18 at 16:19
add a comment |
$begingroup$
Given an $n$-set $Ssubset mathbb R^2$, consider
$$mathscr S = (x,y),.$$
Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by
$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$
The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.
Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.
With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
$endgroup$
Given an $n$-set $Ssubset mathbb R^2$, consider
$$mathscr S = (x,y),.$$
Obviously, $|mathscr S| = binomn2$.
Now, define an equivalence relationship $sim$ on $mathscr S$ by
$$ (x_0,y_0) sim (x_1,y_1) iff d(x_0,y_0) = d(x_1,y_1).$$
The relation $sim$ partitions $mathscr S$ into some number $k$ of classes, each of which has most $U(n)$ elements.
Hence, $k geq leftlceilbinomn2/U(n)rightrceil geq binomn2/U(n)$.
Now, we know there are least $g(n)$ classes.
Suppose that we chose $S$ a priori such that $k = g(n)$.
This is possible, for otherwise $g(n)$ would not be a minimum.
With this choice, the inequality follows.
Notice that the inequality depends on $n$, but not on $S$.
Using our freedom to choose $S$ can make it easier to prove the inequality.
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
edited Apr 2 '18 at 16:10
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
answered Apr 2 '18 at 15:57
FimpellizieriFimpellizieri
17.2k11836
17.2k11836
1
$begingroup$
Really neat, thanks!
$endgroup$
– user547222
Apr 2 '18 at 16:18
$begingroup$
You're welcome! Glad to help.
$endgroup$
– Fimpellizieri
Apr 2 '18 at 16:19
add a comment |
1
$begingroup$
Really neat, thanks!
$endgroup$
– user547222
Apr 2 '18 at 16:18
$begingroup$
You're welcome! Glad to help.
$endgroup$
– Fimpellizieri
Apr 2 '18 at 16:19
1
1
$begingroup$
Really neat, thanks!
$endgroup$
– user547222
Apr 2 '18 at 16:18
$begingroup$
Really neat, thanks!
$endgroup$
– user547222
Apr 2 '18 at 16:18
$begingroup$
You're welcome! Glad to help.
$endgroup$
– Fimpellizieri
Apr 2 '18 at 16:19
$begingroup$
You're welcome! Glad to help.
$endgroup$
– Fimpellizieri
Apr 2 '18 at 16:19
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%2f2718927%2fminimum-number-of-distinct-distances-in-a-plane%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
1
$begingroup$
How does $U(n)$ depend on $n$?
$endgroup$
– Fimpellizieri
Apr 2 '18 at 15:45
$begingroup$
@Fimpellizieri fixed
$endgroup$
– user547222
Apr 2 '18 at 15:46
$begingroup$
Yes, your afterthought is correct. Obviously there are at most $U(n)$ pairs of points that are any given distance apart, by scaling. So there can't be more that $U(n)$ points in any group, so at most $binomn2/U(n)$ groups.
$endgroup$
– saulspatz
Apr 2 '18 at 15:51
$begingroup$
This is pigeon-hole, and in fact I'd even say: Clearly, $g(n)ge 1+nchoose 2/U(n)$ for $nge 2$
$endgroup$
– Hagen von Eitzen
Apr 2 '18 at 15:53