N-dimensional geometric partitioning

  • #1
3,077
3

Main Question or Discussion Point

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:

Answers and Replies

  • #2
damgo
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
191
0
...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
3,077
3
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
damgo
^^^ Can you restate that? I don't understand what you're saying. I can derive my formula if that's what you want....
 
  • #6
3,077
3
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
191
0
The number of polygons is 2^(n+1)-n-2, which increases astronomically against the number of vertices.
 
  • #8
3,077
3
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
damgo
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
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
I've seen the Ackermann function (and boy does it grow fast!), what's the busy beaver function?

Hurkyl
 
  • #11
damgo
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.
 

Related Threads on N-dimensional geometric partitioning

  • Last Post
Replies
20
Views
7K
  • Last Post
Replies
9
Views
5K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
13
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
10
Views
2K
Replies
2
Views
666
Top