Re: how many dimensions do I need?

On Oct 29, 3:07 am, "narutocan...@xxxxxxxxx" <narutocan...@xxxxxxxxx>
wrote:
hi

1. I have n points, each point needs to connect with all the other
points (total of (n-1)! lines), how many diemensions do I need in
general so that no lines are crossed. (lines do not have to be
straight)

For n<=4 you can do this in two dimensions. For n=4 it is a triangle
with a point in the middle connected to each corner. You cannot put
K(5), the complete graph on five points, into the plane. For any n,
you can do this in three dimensions. The point is that lines do not
separate three-space the way they to two-space. So you will get quite
a tangle of spaghetti, but you can put K(n) into three-space.
2. If each point is allowed only m lines (going out or coming in),
what is the minimum dimensions needed (of the n points, two of them
are fully connected to all the other points)?

Again, you only need at most three dimensions. If there are only two
lines per point, you have an n-gon which can be embedded in two-space
without crossing.
3. (related to 2) let's say each point is actually some electronic
component and has only a maximum of m lines going out or in, how many
layers of PCB board are needed? (there are only two points represent
power and ground that connect with every other points)

This is a very different problem, as lines that would cross but be at
the same potential are extraneous. As you point out, you can think of
a power plane that connects some of the points and a power plane that
connects some of the others. Just connect whatever pins you want to
power and what you want to ground. The issue is the traces that are
neither power nor ground-you don't want them to cross. But neither do
you want a complete graph. Some people spend a lot of time on this
problem.

Ross
.

Relevant Pages

  • Re: how many dimensions do I need?
    ... points (total of (n-1)! ... you can do this in three dimensions. ... power and ground that connect with every other points) ... a power plane that connects some of the points and a power plane that ...
    (sci.math)
  • Re: how many dimensions do I need?
    ... points (total of (n-1)! ... what is the minimum dimensions needed (of the n points, ... power and ground that connect with every other points) ... a power plane that connects some of the points and a power plane that ...
    (sci.math)
  • Re: how many dimensions do I need?
    ... points (total of (n-1)! ... you can do this in three dimensions. ... power and ground that connect with every other points) ... a power plane that connects some of the points and a power plane that ...
    (sci.math)
  • Re: placing addiional caps across existing caps to reduce noise
    ... concerned with even low levels of noise in the RF region. ... thought was overkill in the power distribution. ... On the other hand a good power plane will decouple noise at the source ... and prevent it from reaching the ferrite filter. ...
    (comp.arch.fpga)
  • Re: how many dimensions do I need?
    ... Ross A. Finlayson wrote: ... points (total of (n-1)! ... you can do this in three dimensions. ... power and ground that connect with every other points) ...
    (sci.math)