N-dimensional geometric partitioning

  • Thread starter Loren Booda
  • Start date
  • Tags
    Geometric
In summary, given n+1 points in n-dimensional Euclidean space, the number of polytopes that can be defined by representing each point as a possible vertex is 2^(n+1) - n - 2. This is a more rapidly increasing series than that of ordinary partitions, which can be seen through examples such as the Traveling Salesman problem and the Ackermann function. Another example of a rapidly increasing function is the Busy Beaver function, which is provably uncomputable and grows faster than any computable function.
  • #1
Loren Booda
3,125
4
Given n+1 points in n-dimensional Euclidean space, how many polytopes (generalizations of polygons of n to as few as 2 dimensions) may be defined by the representation of each point as a possible vertex?
 
Last edited:
Mathematics news on Phys.org
  • #2
If I'm understanding you correctly, then any combination of 2 or more types would yield a valid polytope.

So 2^(n+1) - 1 - (n+1) = 2^(n+1) - n - 2
 
  • #3
...n...k.....0...1...n+1
sum...C...=2^(n+1)-C...- C...- C...= 2^(n+1)-n-2;
.k=2...n+1.....n+1...n+1...n+1

(using Newton's bynom...(bad english));
Exactly as damgo said...
Take the . as space (' ')
 
Last edited:
  • #4
I am trying to develop a combinatorics which surpasses the progression of partitioning, thus the above definition. Even partitioning does not have an exact heuristic to determine its nth term.

Can anyone show the derivation of an approximate heuristic for this problem, or at least whether the magnitude of its nth term is significantly greater than that of partitions?
 
  • #5
^^^ Can you restate that? I don't understand what you're saying. I can derive my formula if that's what you want...
 
  • #6
Take n+1 points in n dimensions. Count all possible 2-dimensional polygons and their n-dimensional generalizations, formed with any or all points as vertices.

I believe that the count should yield a more rapidly increasing series than that of ordinary partitions. An example of partitioning is the simply stated Traveling Salesman problem, which asks to count the possible paths covering all "cities" on a map. The number of paths increases astronomically against the number of locations.
 
  • #7
The number of polygons is 2^(n+1)-n-2, which increases astronomically against the number of vertices.
 
  • #8
My guess is that the number of polytopes outlined by arbitrary connections between n points in n dimensions is on the order of p[p[n]], where p[n] is the partition of n. Even [p[n]] (recall the "Traveling Salesman" problem) eventually increases much more rapidly than 2^(n+1)-n-2, or any other exponential relation. In turn, p[p[n]] almost immediately reaches incalculable numeration.
 
  • #9
The # of paths in the traveling salesman problem go as Permutations(n) = n! ~ (n/e)^n (Stirling's approx). The # of polytopes is slower, ~2^n , since order does not matter.

If you want to see *really* quickly increasing things, try Ackerman's function, or the Busy Beaver function.
 
  • #10
I've seen the Ackermann function (and boy does it grow fast!), what's the busy beaver function?

Hurkyl
 
  • #11
Consider Turing machines with 2 symbols (call them 0 and 1) and n states, starting on a blank (0's) tape. Look at just the ones that eventually halt with a consecutive series of 1's on the tape. BB(n) is the length of the longest series of 1's produced in this manner.

Roughly, it's the biggest number a computer with n states and infinite storage can create. It's known for n<5... BB(6) is crazy huge, at least 10^100. It's provably uncomputable, and IIRC you can prove that it grows faster (in a rough sense) than any computable function.
 

What is N-dimensional geometric partitioning?

N-dimensional geometric partitioning is a method used in mathematics and computer science to divide a multi-dimensional space into smaller subspaces. This partitioning allows for easier analysis and processing of data in high-dimensional spaces.

What are some common applications of N-dimensional geometric partitioning?

N-dimensional geometric partitioning is commonly used in data mining, image processing, and machine learning. It can also be applied in areas such as computer graphics, computational geometry, and data compression.

How is N-dimensional geometric partitioning different from regular partitioning?

N-dimensional geometric partitioning differs from regular partitioning in that it takes into account the additional dimensions of the space. Regular partitioning only divides a space into smaller sections, while N-dimensional geometric partitioning takes into consideration the relationships and interactions between the different dimensions.

What are some advantages of using N-dimensional geometric partitioning?

N-dimensional geometric partitioning allows for more efficient and accurate analysis of high-dimensional data. It also helps reduce computational complexity and can improve the performance of algorithms in various applications.

Are there any limitations to N-dimensional geometric partitioning?

One limitation of N-dimensional geometric partitioning is that it can be computationally intensive and may not be suitable for very large datasets. Additionally, the effectiveness of this method may depend on the specific dataset and the chosen partitioning technique.

Similar threads

Replies
2
Views
176
  • General Math
Replies
1
Views
265
Replies
2
Views
1K
  • General Math
Replies
8
Views
1K
  • General Math
Replies
2
Views
1K
Replies
3
Views
1K
Replies
12
Views
898
  • General Math
Replies
2
Views
912
  • General Math
Replies
7
Views
887
Replies
4
Views
523
Back
Top