Wikipedia:Reference desk/Archives/Mathematics/2008 August 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 17

Connecting points without intersecting lines

Is there an algorithm out there, or some sort of theory for me to read up on, which gives a method of connecting n points using n-1 lines without any of these lines intersecting? Thanks in advance. Not homework, just a curiosity. x42bn6 Talk Mess 04:13, 17 August 2008 (UTC)

The first thing that comes to mind is convex hulls. That is, you could take the convex hull of the set, remove any points connected by that, and interate inwards. Once you have a sequence of nonintersecting loops that cover all the points, it's just a matter of removing a link from each loop and connecting them up going outwards to get a nice spiral. Black Carrot (talk) 04:33, 17 August 2008 (UTC)

Here's another approach (I'm assuming you're in two dimensions). First suppose that no two points have the same y-coordinate. Order the points by increasing y-coordinate, and then connect consecutive points in this list. If some two points have the same y-coordinate value, then you can (1) rotate all points (around the origin, say) by some angle such that no two points have the same y-coordinate (such an angle must exist), then (2) connect the points as above, then (3) unrotate the points by the same angle. A similar approach should work in any number of dimensions of Euclidean space.

If you specifically want to find the connections that minimize the total length of the n-1 lines, then look at minimum spanning trees. Eric. 80.101.159.204 (talk) 12:49, 17 August 2008 (UTC)

A minimum spanning tree of a planar graph weighted by Euclidean distance will not self-intersect. Proof: suppose it does, and let AC and BD be intersecting line segments in the MST. Remove them from the graph. Since the original tree was connected there must still be a path connecting (A,B) or (C,D) or (B,C) or (D,A). By symmetry we may as well suppose it's (A,B). Case 1: A, B, C, D are in general position. Then adding the edges (A,D) and (B,C) to the reduced graph yields another spanning tree, and by the triangle inequality it's shorter than the one we started with, which is a contradiction. Case 2 (three collinear and one not) and case 3 (all collinear) yield similar contradictions, and we're done. This proof assumes all the points are distinct. If they're not, there might be no non-self-intersecting spanning tree depending on how you define self-intersection. -- BenRG (talk) 14:59, 17 August 2008 (UTC)

I don't think that's quite enough for a proof: the new edges might create new intersections, which would then have to be resolved. To complete the proof, you'd actually have to show that the process eventually terminates (or, for infinite graphs, that any finite subset of the graph will stabilize with no intersections after finitely many steps).

It's fairly simple to prove (by building the tree one node at a time) that any set of points on the plane has a non-intersecting spanning tree. It's slightly harder to show that the minimum-distance tree must be non-intersecting, though it seems intuitively obvious. —Ilmari Karonen (talk) 18:30, 17 August 2008 (UTC)

No, that proof works fine. The point is that any spanning tree with self-intersections is not of minimal weight, so any minimal spanning tree must be non-self-intersecting. There's no step-by-step process involved. It only works for finite graphs, but that's all the OP asked about. Of course, finding an MST is going to be far slower than Eric's trivial algorithm. Algebraist 18:39, 17 August 2008 (UTC)

Planar graph might be a good article to read, by the way. 67.135.207.2 (talk) 22:43, 19 August 2008 (UTC)

Square root of i

I have read the article on i and have seen what the square root of i is but the article only discusses how to show that such and such is the square root of i; it doesn't actually show how you can determine the square root by yourself. Can anyone shed some light on the issue? 92.4.196.6 (talk) 18:55, 17 August 2008 (UTC)

There are a number of ways. For example, you could write the square root of i as a+bi, deduce that a²=b² and 2ab=1, and solve for a and b. Or you could write i as $e^{\frac {i\pi }{2}}$, and deduce that $e^{\frac {i\pi }{4}}$ is a square root of i, and hence that $-e^{\frac {i\pi }{4}}$ is the other one. Algebraist 18:59, 17 August 2008 (UTC)

You might find it interesting that i^i is real- try to prove this yourself using the fact that e^(i*pi/2) = i (which is what algebraist said).

Topology Expert (talk) 03:43, 20 August 2008 (UTC)

When dealing with complex numbers it's often useful to think geometrically (see argand diagram). In that context, multiplying by i means "rotate 90 degrees anticlockwise". Then it's clear that multiplying by the square root of i must be a 45 degree rotation (so that when you do it twice (ie. square it) you get a 90 degree rotation). Then you can use basic trig to work out what point you get to by rotating 1 by 45 degrees anticlockwise, and you find that it's $\cos(45)+i\sin(45)$ (actually, you don't need trig, Pythagoras' theorem combined with some observations about symmetries is enough - try drawing a diagram). --Tango (talk) 21:12, 17 August 2008 (UTC)

To be precise, I ought to say either 45 degrees, or 225 degrees - there are, of course, two square roots. --Tango (talk) 21:14, 17 August 2008 (UTC)

There is an easy way to figure out the square root of i.

• In the mathematics of complex numbers, cis θ is an abbreviation for cos θ + i·sin θ —Preceding unsigned comment added by 211.28.51.233 (talk) 10:39, 18 August 2008 (UTC)

First, imagine that multiplying by a complex number z = x + y i = r cis(theta) can be represented geometrically by two geometric operations.

Operation one is ROTATION

Operation two is SCALING

Now first z = i means that x=0 and y=1 also be represented as r = 1 and theta = 90deg

Now find the solution zans = rans cis( thetaans ) such that

2 * thetaans = 90deg + k * 360deg where k is an integer

and

rans^2 = 1

Basically what I am saying is "find a rotation angle (thetaans) such that when it is rotated twice, it had rotated 90 degrees".

Next I say "find a non-negative scaling factor (rans) such that when it scale up twice in a row, it scales up by 1".

Thus the square root of i is zans

I find (Please note that there are TWO solutions)

thetaans = 45deg (the obvious answer) or thetaans = -135deg (the not so obvious answer)

rans = 1

So zans = 1 cis( 45deg) or zans = 1 cis ( -135deg )

211.28.51.233 (talk) 10:37, 18 August 2008 (UTC)

Infinity

I just been thinking about infinity. And I wondered what is the infintith root (know what i mean) of infinity?--79.76.130.174 (talk) 19:09, 17 August 2008 (UTC)

$\infty ^{0}$ is an indeterminate form, q.v. That's not exactly an answer to your question, but it's probably the closest thing to an answer that you're really going to get. --Trovatore (talk) 19:24, 17 August 2008 (UTC)

A related question might be whether $\lim _{x\to \infty }x^{1/x}=1$. It seems to approach 1, but I am not certain that it monotonically decreases as x increases. - Rainwarrior (talk) 19:50, 17 August 2008 (UTC)

Correct me if I make any mistakes...

$\lim _{x\to \infty }x^{1/x}=\exp \left[\lim \ln \left(x^{1/x}\right)\right]$

$=\exp \left[\lim {\frac {\ln x}{x}}\right]$

$=\exp \left[\lim {\frac {(1/x)}{1}}\right]$

$=\exp \left[0\right]$

$=1$

I used L'hopitals rule in there. The limits are all taken as x goes to infinity. Eric. 80.101.159.204 (talk) 20:18, 17 August 2008 (UTC)

That's fine if you assume that base and exponent approach infinity and zero in such a way that they have a constant product. But what if the base increases as a^x while the exponent decreases as 1/x ? In that case the limit is a. So you can make the limit equal whatever you like - as -Trovatore said, it is indeterminate. Gandalf61 (talk) 20:38, 17 August 2008 (UTC)

But the base is x, which increases as x, not as anything else... I don't understand you... --Tango (talk) 21:06, 17 August 2008 (UTC)

The assumption was that the "infinitieth root of zero" can be interpreted as

$\infty ^{0}=\lim _{x\to \infty }x^{1/x}=1$

but an equaly valid interpretation of the "infinitieth root of zero" is

$\infty ^{0}=\lim _{x\to \infty }(a^{x})^{1/x}=a$

Gandalf61 (talk) 21:14, 17 August 2008 (UTC)

Rainwarrior only claimed it was a related question, not the same question. --Tango (talk) 21:15, 17 August 2008 (UTC)

Fine. Ignore what I said. Gandalf61 (talk) 21:20, 17 August 2008 (UTC)

I'm not certain I know what you mean. Viewing the problem in terms of limits, you can ask what happens as each argument grows without bound, in which case the answers are all over the map. On the other hand, you can also view 'infinity' as a number in its own right, or at least a formal symbol, in which case the infinity-ith root of infinity would be exactly that. Black Carrot (talk) 07:55, 18 August 2008 (UTC)

"the infintith root of infinity" is written ${\sqrt[{\infty }]{\infty }}.$ It should be approximated by a huge root of a huge number, ${\sqrt[{a}]{b}},$ but there is no well defined limit to that expression. If a goes to infinity first and b afterwards, then the limit is one, $\lim _{b\rightarrow \infty }\lim _{a\rightarrow \infty }{\sqrt[{a}]{b}}=1,$ while if b goes to infinity first and a afterwards, then the limit is infinite: $\lim _{a\rightarrow \infty }\lim _{b\rightarrow \infty }{\sqrt[{a}]{b}}=\infty ,$ and if a and b goes towards infinity together, then the result can be anything in between depending on the functional relationship between a and b. That is why ${\sqrt[{\infty }]{\infty }}$ is called an indeterminate form; it is a mathematical expression that does not define a value. Bo Jacoby (talk) 16:44, 21 August 2008 (UTC).

This is likely a stupid question, but what about ${\sqrt[{\infty }]{\infty }}!$

Wanderer57 (talk) 17:23, 21 August 2008 (UTC)

You mean the factorial? Factorials are only defined for natural numbers, an indeterminate form is not a natural number, so it's simply undefined. --Tango (talk) 02:14, 22 August 2008 (UTC)

I assume you meant to say ${\sqrt[{\infty }]{\infty !}}$, with the factorial under the root. You can interpret $x!$ as $\Gamma (x+1)$ (see Gamma function), so the expression essentially becomes $\lim _{x\to \infty }{\sqrt[{x}]{\Gamma (x+1)}}$, which is $\infty$. Of course, this assumes that both of the infinities in ${\sqrt[{\infty }]{\infty !}}$ are the same $x$, so they go to infinity at the same rate. —Bkell (talk) 15:58, 23 August 2008 (UTC)