Finding unusually large empty regions in a field of coordinate points?
$begingroup$
I have a list of coordinates representing arbitrary points in space.
[0.2, 0.55],
[1.23, 4.56],
[7, 8],
...
I want to find two things: regions with no points that are especially large, and collated separately, large regions with especially few points.
For example: In this image, Fig 1 shows a sample field of points. Fig 2 shows the same field of points, but denoted with red circles indicating large regions that have no points.
I am looking for a function which, given the coordinates for Fig 1, returns coordinates one could use to produce Fig 2. (Not illustrated here: the large regions with few points result.)
Here are a few constraints to work with.
- We can assume the space is flat. (It's not curved or circular.)
- But the space may have any number of dimensions >= 2
- The space should be bounded by the outermost points.
- We should not highlight regions that clip outside that boundary.
- The preferred geometry for the highlighted regions is spherical, but that's not a hard requirement.
I initially sought to solve this problem in the following two ways:
By subdivision: Subdivide the space into equal regions (n-orthotopes). Then count the number of points in the subdivision volume. Take the average number of points-per-subdivision at this scale, then look for subdivisions that have lower than a standard devision of points, and add it to my list of candidates. The subdivide the subdivisions, and repeat down to a minimum scale. Sort the list of candidates to find the volumes that best meet my criteria.
By random sampling: Choose a point at random within the space. Choose a random radius value so that we describe an n-sphere at that point. Count the number of points within the n-sphere volume. Keep doing this up to some maximum defined number of iterations, then sort the list to find the volumes that best meet my criteria. (I like this idea better than the subdivision one, for its relative simplicity.)
But I thought I would ask Mathematics SE in case there is a known solution to this kind of problem. Is there an established/solved/common/conventional way to do this?
geometry algorithms
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
$endgroup$
add a comment |
$begingroup$
I have a list of coordinates representing arbitrary points in space.
[0.2, 0.55],
[1.23, 4.56],
[7, 8],
...
I want to find two things: regions with no points that are especially large, and collated separately, large regions with especially few points.
For example: In this image, Fig 1 shows a sample field of points. Fig 2 shows the same field of points, but denoted with red circles indicating large regions that have no points.
I am looking for a function which, given the coordinates for Fig 1, returns coordinates one could use to produce Fig 2. (Not illustrated here: the large regions with few points result.)
Here are a few constraints to work with.
- We can assume the space is flat. (It's not curved or circular.)
- But the space may have any number of dimensions >= 2
- The space should be bounded by the outermost points.
- We should not highlight regions that clip outside that boundary.
- The preferred geometry for the highlighted regions is spherical, but that's not a hard requirement.
I initially sought to solve this problem in the following two ways:
By subdivision: Subdivide the space into equal regions (n-orthotopes). Then count the number of points in the subdivision volume. Take the average number of points-per-subdivision at this scale, then look for subdivisions that have lower than a standard devision of points, and add it to my list of candidates. The subdivide the subdivisions, and repeat down to a minimum scale. Sort the list of candidates to find the volumes that best meet my criteria.
By random sampling: Choose a point at random within the space. Choose a random radius value so that we describe an n-sphere at that point. Count the number of points within the n-sphere volume. Keep doing this up to some maximum defined number of iterations, then sort the list to find the volumes that best meet my criteria. (I like this idea better than the subdivision one, for its relative simplicity.)
But I thought I would ask Mathematics SE in case there is a known solution to this kind of problem. Is there an established/solved/common/conventional way to do this?
geometry algorithms
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
$endgroup$
$begingroup$
How long is your list? Are we talking about hundreds or thousands or even millions of coordinates?
$endgroup$
– Oldboy
Dec 27 '18 at 19:21
$begingroup$
I will have lists of thousands of (high-dimensional) coordinates.
$endgroup$
– GladstoneKeep
Dec 27 '18 at 20:58
add a comment |
$begingroup$
I have a list of coordinates representing arbitrary points in space.
[0.2, 0.55],
[1.23, 4.56],
[7, 8],
...
I want to find two things: regions with no points that are especially large, and collated separately, large regions with especially few points.
For example: In this image, Fig 1 shows a sample field of points. Fig 2 shows the same field of points, but denoted with red circles indicating large regions that have no points.
I am looking for a function which, given the coordinates for Fig 1, returns coordinates one could use to produce Fig 2. (Not illustrated here: the large regions with few points result.)
Here are a few constraints to work with.
- We can assume the space is flat. (It's not curved or circular.)
- But the space may have any number of dimensions >= 2
- The space should be bounded by the outermost points.
- We should not highlight regions that clip outside that boundary.
- The preferred geometry for the highlighted regions is spherical, but that's not a hard requirement.
I initially sought to solve this problem in the following two ways:
By subdivision: Subdivide the space into equal regions (n-orthotopes). Then count the number of points in the subdivision volume. Take the average number of points-per-subdivision at this scale, then look for subdivisions that have lower than a standard devision of points, and add it to my list of candidates. The subdivide the subdivisions, and repeat down to a minimum scale. Sort the list of candidates to find the volumes that best meet my criteria.
By random sampling: Choose a point at random within the space. Choose a random radius value so that we describe an n-sphere at that point. Count the number of points within the n-sphere volume. Keep doing this up to some maximum defined number of iterations, then sort the list to find the volumes that best meet my criteria. (I like this idea better than the subdivision one, for its relative simplicity.)
But I thought I would ask Mathematics SE in case there is a known solution to this kind of problem. Is there an established/solved/common/conventional way to do this?
geometry algorithms
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
$endgroup$
I have a list of coordinates representing arbitrary points in space.
[0.2, 0.55],
[1.23, 4.56],
[7, 8],
...
I want to find two things: regions with no points that are especially large, and collated separately, large regions with especially few points.
For example: In this image, Fig 1 shows a sample field of points. Fig 2 shows the same field of points, but denoted with red circles indicating large regions that have no points.
I am looking for a function which, given the coordinates for Fig 1, returns coordinates one could use to produce Fig 2. (Not illustrated here: the large regions with few points result.)
Here are a few constraints to work with.
- We can assume the space is flat. (It's not curved or circular.)
- But the space may have any number of dimensions >= 2
- The space should be bounded by the outermost points.
- We should not highlight regions that clip outside that boundary.
- The preferred geometry for the highlighted regions is spherical, but that's not a hard requirement.
I initially sought to solve this problem in the following two ways:
By subdivision: Subdivide the space into equal regions (n-orthotopes). Then count the number of points in the subdivision volume. Take the average number of points-per-subdivision at this scale, then look for subdivisions that have lower than a standard devision of points, and add it to my list of candidates. The subdivide the subdivisions, and repeat down to a minimum scale. Sort the list of candidates to find the volumes that best meet my criteria.
By random sampling: Choose a point at random within the space. Choose a random radius value so that we describe an n-sphere at that point. Count the number of points within the n-sphere volume. Keep doing this up to some maximum defined number of iterations, then sort the list to find the volumes that best meet my criteria. (I like this idea better than the subdivision one, for its relative simplicity.)
But I thought I would ask Mathematics SE in case there is a known solution to this kind of problem. Is there an established/solved/common/conventional way to do this?
geometry algorithms
geometry algorithms
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
asked Dec 27 '18 at 19:05
GladstoneKeepGladstoneKeep
1455
1455
$begingroup$
How long is your list? Are we talking about hundreds or thousands or even millions of coordinates?
$endgroup$
– Oldboy
Dec 27 '18 at 19:21
$begingroup$
I will have lists of thousands of (high-dimensional) coordinates.
$endgroup$
– GladstoneKeep
Dec 27 '18 at 20:58
add a comment |
$begingroup$
How long is your list? Are we talking about hundreds or thousands or even millions of coordinates?
$endgroup$
– Oldboy
Dec 27 '18 at 19:21
$begingroup$
I will have lists of thousands of (high-dimensional) coordinates.
$endgroup$
– GladstoneKeep
Dec 27 '18 at 20:58
$begingroup$
How long is your list? Are we talking about hundreds or thousands or even millions of coordinates?
$endgroup$
– Oldboy
Dec 27 '18 at 19:21
$begingroup$
How long is your list? Are we talking about hundreds or thousands or even millions of coordinates?
$endgroup$
– Oldboy
Dec 27 '18 at 19:21
$begingroup$
I will have lists of thousands of (high-dimensional) coordinates.
$endgroup$
– GladstoneKeep
Dec 27 '18 at 20:58
$begingroup$
I will have lists of thousands of (high-dimensional) coordinates.
$endgroup$
– GladstoneKeep
Dec 27 '18 at 20:58
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Construct the Voronoi partition of your space. If your circle is centered in the region around point $p$, as you grow its radius, it will meet point $p$ first. Therefore, maximal circles are where three or more regions meet (i.e. are vertices in the partition). There are finitely many such vertices, so you can find the distance from each to the equidistant points giving any of the regions meeting at that vertex and sort these from largest to smallest.
Note that higher order Voronoi diagrams can meet your requirement for large regions containing a few points.
Lloyd's algorithm can be used to compute Voronoi diagrams in arbitrary dimensions. In the plane, Fortune's algorithm is (asymptotically and practically) faster.
Software for computing (higher order) Voronoi diagrams exists. I make no representation of fitness for the following Google search results.
- "Higher Order Voronoi Diagrams" in C/C++ using GLUT and Paul Rademacher's GLUI libraries for Linux.
- (plain, not higher-order) "scipy.spatial.Voronoi" in Python.
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
$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%2f3054267%2ffinding-unusually-large-empty-regions-in-a-field-of-coordinate-points%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$
Construct the Voronoi partition of your space. If your circle is centered in the region around point $p$, as you grow its radius, it will meet point $p$ first. Therefore, maximal circles are where three or more regions meet (i.e. are vertices in the partition). There are finitely many such vertices, so you can find the distance from each to the equidistant points giving any of the regions meeting at that vertex and sort these from largest to smallest.
Note that higher order Voronoi diagrams can meet your requirement for large regions containing a few points.
Lloyd's algorithm can be used to compute Voronoi diagrams in arbitrary dimensions. In the plane, Fortune's algorithm is (asymptotically and practically) faster.
Software for computing (higher order) Voronoi diagrams exists. I make no representation of fitness for the following Google search results.
- "Higher Order Voronoi Diagrams" in C/C++ using GLUT and Paul Rademacher's GLUI libraries for Linux.
- (plain, not higher-order) "scipy.spatial.Voronoi" in Python.
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
$endgroup$
add a comment |
$begingroup$
Construct the Voronoi partition of your space. If your circle is centered in the region around point $p$, as you grow its radius, it will meet point $p$ first. Therefore, maximal circles are where three or more regions meet (i.e. are vertices in the partition). There are finitely many such vertices, so you can find the distance from each to the equidistant points giving any of the regions meeting at that vertex and sort these from largest to smallest.
Note that higher order Voronoi diagrams can meet your requirement for large regions containing a few points.
Lloyd's algorithm can be used to compute Voronoi diagrams in arbitrary dimensions. In the plane, Fortune's algorithm is (asymptotically and practically) faster.
Software for computing (higher order) Voronoi diagrams exists. I make no representation of fitness for the following Google search results.
- "Higher Order Voronoi Diagrams" in C/C++ using GLUT and Paul Rademacher's GLUI libraries for Linux.
- (plain, not higher-order) "scipy.spatial.Voronoi" in Python.
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
$endgroup$
add a comment |
$begingroup$
Construct the Voronoi partition of your space. If your circle is centered in the region around point $p$, as you grow its radius, it will meet point $p$ first. Therefore, maximal circles are where three or more regions meet (i.e. are vertices in the partition). There are finitely many such vertices, so you can find the distance from each to the equidistant points giving any of the regions meeting at that vertex and sort these from largest to smallest.
Note that higher order Voronoi diagrams can meet your requirement for large regions containing a few points.
Lloyd's algorithm can be used to compute Voronoi diagrams in arbitrary dimensions. In the plane, Fortune's algorithm is (asymptotically and practically) faster.
Software for computing (higher order) Voronoi diagrams exists. I make no representation of fitness for the following Google search results.
- "Higher Order Voronoi Diagrams" in C/C++ using GLUT and Paul Rademacher's GLUI libraries for Linux.
- (plain, not higher-order) "scipy.spatial.Voronoi" in Python.
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
$endgroup$
Construct the Voronoi partition of your space. If your circle is centered in the region around point $p$, as you grow its radius, it will meet point $p$ first. Therefore, maximal circles are where three or more regions meet (i.e. are vertices in the partition). There are finitely many such vertices, so you can find the distance from each to the equidistant points giving any of the regions meeting at that vertex and sort these from largest to smallest.
Note that higher order Voronoi diagrams can meet your requirement for large regions containing a few points.
Lloyd's algorithm can be used to compute Voronoi diagrams in arbitrary dimensions. In the plane, Fortune's algorithm is (asymptotically and practically) faster.
Software for computing (higher order) Voronoi diagrams exists. I make no representation of fitness for the following Google search results.
- "Higher Order Voronoi Diagrams" in C/C++ using GLUT and Paul Rademacher's GLUI libraries for Linux.
- (plain, not higher-order) "scipy.spatial.Voronoi" in Python.
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
edited Dec 27 '18 at 21:15
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
answered Dec 27 '18 at 21:02
Eric TowersEric Towers
33.9k22370
33.9k22370
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%2f3054267%2ffinding-unusually-large-empty-regions-in-a-field-of-coordinate-points%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
$begingroup$
How long is your list? Are we talking about hundreds or thousands or even millions of coordinates?
$endgroup$
– Oldboy
Dec 27 '18 at 19:21
$begingroup$
I will have lists of thousands of (high-dimensional) coordinates.
$endgroup$
– GladstoneKeep
Dec 27 '18 at 20:58