[algogeeks] Re: Testing if 3 points form a triangle
Hi BiGYaN, triangle is a 2D object which can be formed by any 3 non- collinear points. It can exist in 4D, just like a point existing in 3D. On May 31, 2:11 am, Victor Carvalho [EMAIL PROTECTED] wrote: Feng, how can form a triangle in four dimensions??? 2007/5/29, BiGYaN [EMAIL PROTECTED]: Just test whether they are collinear or not i.e. get the slopes, m1 from 1st and 2nd point m2 from 2nd and 3rd point if m1==m2 then they do not form a triangle else they do Computing the area of the triangle and testing for 0 might also work but I feel that the computation will be bigger -- Victor Carvalho Computação - UFC GELSoL - Grupo de Estudos de Linux e Software Livre E-Jr Empresa Júnior de Computação --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Testing if 3 points form a triangle
Hi all! Given 3 points in 3D, what is the fast and numerically stable way to test if they form a triangle? I am thinking computing the determinant of the square matrix formed by the 3 points and testing if the determinant is nonzero. But I am not sure. What about the case for high dimensions, i.e. 4D, 5D ... Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Travelling Salesman Relaxation
As far as I know, TSP has a PTAS, which is based on DP. This resultwas made by Arora http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-854JFall2001/334C4A2D-D89F-460F-9D02-017657FF0759/0/arora.pdf On 7/13/06, Ioannis Atsonios [EMAIL PROTECTED] wrote: one type of relaxation is based on triangle inequality.e.gw(x1,x2)+w(x2,x3)w(x1,x3),where x1,x2,x3 are nodes(often called as euclidean tsp),Christofides gave an algorithm with approximation ratio1.5.Also there are a lot of variants,you must have in mind that tsp isnp-complete ,even if the weights of node is 1,2,3(integers)prooved by Yannakakis,Papadimitriou. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Help me with this problem
On 6/23/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: If M = N and M = K, then the solution isN * (M/K) + (M - M/K*K) * (N/K)Use integer division This solution is not corrent. for example, M = N = 4, K = 2 N * (M/K) + (M - M/K*K) * (N/K) = 4 * ( 4 / 2 ) + ( 4 - 4 / 2 * 2 ) * ( 4 / 2 ) = 8 But the number of placement is greater than 8 1122 3344 5566 7788 1322 1344 5566 7788 1124 3324 5566 7788 1324 1324 5566 7788 .. easy to see that we can get another 4 ways of placement following upper mode But another group of placements is like this: 1223 1443 5566 7788 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: a problem
I think that Greedy algorithm can resolve this problem and get the optimal solution. On 6/17/06, Thomas.Chang [EMAIL PROTECTED] wrote: suppose a number sequence, for example:4, 1, 5, 9, 2, 3the task is to devide it into as less groups as possible so that in each group the numbers are sorted incrementally without changing theoriginal order.for example, the above sequence can be devided into:4, 5, 9,1, 2, 32 groups in all.How to solve this problem? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting flash puzzles
Carefully choose the position and angle of two ball, and listen! On 6/14/06, Burak Durmuş [EMAIL PROTECTED] wrote: i couldn't solve 2nd puzzle. what am i missing? 2006/6/13, Feng [EMAIL PROTECTED]: beautiful! But the later puzzles is not as difficult as expected. Maybe the modeof increasing difficulty is better. Regards On 6/6/06, Abhi [EMAIL PROTECTED] wrote: http://fizzlebot.com/cdt2.php --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting flash puzzles
beautiful! But the later puzzles is not as difficult as expected. Maybe the modeof increasing difficulty is better. Regards On 6/6/06, Abhi [EMAIL PROTECTED] wrote: http://fizzlebot.com/cdt2.php --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find an iterative method to do the traversal of a binary search tree (inorder say)....
But to setup a threaded binary tree needs to traval the whole tree first.On 5/13/06, thomas [EMAIL PROTECTED] wrote: Feng wrote: When you visit a node N which has two children ( binary tree, for example ) L(N) and R(N), if the next step is visiting L(N), then save L(N) and make L(N) points to N's father which has been saved before. The pointers to fathers take place of stack or recursion. On 5/13/06, Manu [EMAIL PROTECTED] wrote: Find an iterative method to do the traversal of a tree (inorder say) without using recursion and without using stack... A threaded binary tree may be what he needs. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: 100 programmers
Can any body do me a favour? I can't understand the Sultan's dowry problem. If the maximum number can be any of them with equal probability, then we have only 1/n chance which is definite to choose the maximum one. Did I miss something?
