[algogeeks] Re: Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
On Mar 11, 9:33 am, saurabh agrawal saurabh...@gmail.com wrote:
Given an integer n , you have to print all the ways in which n can be
represented as sum of positive integers
I suggest you
1) generate the numeric partitions of n.
That's the lists of numbers in sorted order whose sum is n.
e.g. The numeric partitions of 3 are: {(1,1,1), (1,2), 3}
2) For each partition generate its multiset permutations.
Note: there is a formula for how many of sums of positive integers to
n
there are but I don't what it is.
Regards,
Ralph Boland
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: first larger element in unsorted array...
On Jan 31, 11:17 am, ritu ritugarg.c...@gmail.com wrote:
@Ralph
Build a data structure on array B[1..n] in O(n) time such that
the following problem can be solved in O(log n) time:
Given an index i and value v, find the index j of the first
element in B such that j = i and B[j] v.
Return -1 if no such j exists.
then it ll take n*lg(n) time ... while a o(n) solution exists
Your comment makes no sense given that I posted a (slightly)
different problem. In the original problem there is no v!
Of particular importance the value v is not provided until after
the data structure is constructed. For the record the O(log n) time
cost for a query is optimal. (Admittedly I never actually proved
this.)
Regards,
Ralph Boland
On Jan 31, 9:25 pm,RalphBolandrpbol...@gmail.com wrote:
On Jan 30, 11:00 pm, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity:O(n)
I solved a version of this problem in my thesis.
Build a data structure on array B[1..n] in O(n) time such that
the following problem can be solved in O(log n) time:
Given an index i and value v, find the index j of the first
element in B such that j = i and B[j] v.
Return -1 if no such j exists.
I have an application of this data structure in my thesis (which
is why I invented it) but I would love to hear other applications.
RalphBoland
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sorted 2-d array
On Jun 7, 8:49 am, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: We can do it in O(n * log n) by individually binary-searching for zero on each of the rows. Once we get the index of the first position where zero appears, counting the number of negative number is straight-forward. Here is an even better O(N) algorithm which is very elegant: Consider the bottom-left element of the given 2-D array. If it is negative, the whole of first-column is negative. So we can add that count and ignore that column from then onwards. If it is non-negative, the whole of last-row is non-negative. So we can ignore that row without changing the count. Therefore, by just doing one comparison we are able to eliminate one row or one column. We can iteratively follow this approach and it will terminate in exactly 2*N steps. I must say that your algorithm is very clever since I never thought of it. :-) I thought of a different approach that can be combined with yours to, oddly enough, get an even better solution. Consider the bottom-left element of the given 2-D array. If it is negative: Search the bottom row for the first non-negative value. If this element is the kth then it can be found in O(log k) time using a variation of binary search. Now the first k - 1 columns are all negative so we count those. If it is non-negative: Search the first column bottom to top for the first negative value. If this element is the jth from the bottom then it can be found in O(log j) time. Now the last j-1 rows are all non-negative so they need not be counted. Now follow this approach and it will terminate in O(N) steps. This is no better than your approach in the worst case (in fact slightly worse) but can be much better for cases where either most of the elements are positive or most of the elements are negative. For example if all elements are negative the algorithm runs in O(log N) time (actually 2 log N + O(1)). Open problem: I am guessing that my algorithm is optimal in some (reasonable) sense in which your algorithm is not. Define optimal (reasonably) than then prove that my algorithm is indeed optimal or show that some other algorithm is better by your definition. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: another google telephone interview question
On May 21, 7:17 am, Bharath bharath1...@gmail.com wrote: Find the median of the values and move the lower values to left and higher values to the right. This can be done in o(n). now do the same on both the parts recursively. And the total complexity will be o(nlogk). Very good! I never thought of this even though I knew you could make quicksort be O(n log(n)) by using the the median as the pivot point. Of course I'm sure everyone realizes that one needs to stop the recursion when all the elements in a subarray are the same. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: another google telephone interview question
On May 21, 7:17 am, Bharath bharath1...@gmail.com wrote: Find the median of the values and move the lower values to left and higher values to the right. This can be done in o(n). now do the same on both the parts recursively. And the total complexity will be o(nlogk). Further to my previous post, one question. Can the median be found in O(n) time without using extra memory? I am not familiar with the algorithms that find the median though I know the median can be found in O(n) time. Regards, Ralph -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: tree from linked list
On May 14, 9:46 pm, Yalla Sridhar sridhar2...@gmail.com wrote: @atul linked list can be converted to array with O(n) both space @ time overhead. then tree can be built in O(n) This is true but is not the simplest solution. As pointed out earlier by me and also Divya Jain the best solution is to build the tree bottom up. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Complexity of Algorithms
prove that the average case performance of quicksort is theta(n * log(n)). ... Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: tree from linked list
On May 2, 7:08 am, divya sweetdivya@gmail.com wrote: u are given a sorted lnked list construct a balanced binary search tree from it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. There is a simple iterative solution to this problem that obviously runs in linear time. I have implemented a version of it that builds a weighted binary tree. I'll refrain from describing it here though because I suspect this is someones homework. :-) I will give this clue though. The tree is built bottom up, not top down which is more difficult. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Largest span of Increasing Pair in an array
On Mar 15, 10:07 am, saurabh gupta sgup...@gmail.com wrote: while you scan the array maintain four indices plus two lengths two indices and a length mark one sub-array - start,end, length each such sub-array indicates a non-decreasing sequence, call them S1 and S2. while one scans, S2 keeps track of incoming elements (curr sequence) S1 keeps track of the maximum length (along with indices) so far (prev sequence) as one encounters an element which is less than the previous element, this marks the end of S2, S1 replaces S2 if len S2 len S1 else S2 starts afresh from this new element. In the end if len S2 len S1 answer = S2 else answer = S1. PS: In the beginning and till one encounters a smaller element than the prev one for the first time, S1 = S2 I agree that this is a nice algorthithm that solves the largest non decreasing sequence problem. However, I don't agree that this solves the problem originally posted. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Largest span of Increasing Pair in an array
On Mar 14, 7:46 am, ASHISH MISHRA meetcoolash...@gmail.com wrote: @ankur how u can solve it in o(n) i suppose u need atleast o(n lgn) On Sun, Sep 6, 2009 at 2:52 PM, ankur aggarwal ankur.mast@gmail.comwrote: o(n) is the best sol known to me.. On Sun, Sep 6, 2009 at 1:54 PM, Pramod Negi negi.1...@gmail.com wrote: i guess sorting will do the work. any other constraint?? On Sun, Sep 6, 2009 at 9:52 AM, p0r$h 1987.shis...@gmail.com wrote: Given an array of integers A[N], find the maximum value of (j-k) such that A[k] = A[j] jk. I am looking for a solution with time complexity better than O(N^2). I don't know how to solve this in the claimed O(N) time. However, I have coded a data structure that, given j, will find k in O(log(N)) time. With it you can solve your problem in O(N log N) time. The data structure is built in O(N) time and space. It is part of a larger data structure that I will implement and release as open source in a few months. Regards, Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Interview question.Provide the solution as per the constraints.
This can be done without the parent pointer though the method
may not be wise. As you traverse the tree downward you set
the child pointer you traverse to point to the parent (grandparent
of the child). When you
traverse upward you reset the pointer of the node you traverse
to point to its original child. Now no parent pointers are needed
and no recursion either. The catch is that if your code does
not complete for any reason the tree is cooked.
Charcoal anyone?
On Mar 8, 5:37 am, Terence technic@gmail.com wrote:
What is the storage structure of your BST?
If each node contains pointers to its left child, right child and
parent, then we can traverse through the tree without recursive or stack.
in_order_traverse()
{
p = root;
last = root-parent = NULL;
while(p) {
if (last == p-parent) { // enter
if(p-left) {
last = p; p = p-left;
} else if(p-right) {
process(p);
last = p; p = p-right;
} else {
process(p);
last = p; p = p-parent;
}
} else if (last == p-left) {
process(p);
if(p-right) {
last = p; p = p-right;
} else if(p-right) {
last = p; p = p-parent;
}
} else {
last = p; p = p-parent;
}
}
}
Combine this with Rahul Singh's algorithm lead to a solution with O(n)
time and O(1) memory
On 2010-3-8 15:11, Nikhil Agarwal wrote:
@all: you cannot traverse through the tree recursively because it has
been mentioned that no extra memory (in recursive calls or stack ) is
allowed.
On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta
1989.gau...@googlemail.com mailto:1989.gau...@googlemail.com wrote:
Median of BST means : median of Sorted array of elements? is it?
Convert BST into Hight Balance Search Tree then root node will be
your median.
On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp
nikhil.bhoja...@gmail.com mailto:nikhil.bhoja...@gmail.com wrote:
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
-No extra memory.
Algorithm should be efficient in terms of complexity.
Write a solid secure code for it.
No extra memory--u cannot use stacks to avoid recursion.
No static,global--u cannot use recursion and keep track of the
elements visited so far in inorder.
--
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 mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Junior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find nearest point
On Nov 17, 7:09 am, Tiago Reul tiagor...@gmail.com wrote: Suppose that you have the position of each person in the world. Position is the pair (latitude, longitude). How to represent the data so that I can find the nearest person from a point (φ,λ) without comparing to every pair in the collection? The standard solution to this problem is to use a Voronoi diagram. I am only familiar with the Euclidean version but I see no problem constructing a Voronoi diagram on the surface of a sphere. Ralph Boland -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=.
[algogeeks] Re: minimum difference.
On Sep 1, 7:05 am, ankur aggarwal ankur.mast@gmail.com wrote: given a array of length n. find 2 number such that their differnce is minimum. As already pointed out sorting and then comparing adjacent elements gives you an O(n log n) algorithm. If you have a likelyhood of duplicates then heapsort might be better since the heap can be built in linear time and the sort phase can be aborted if a duplicate element is found. Alternatively one could put your elements into a set (using hashing) and stop immediately if you discover a duplicate by adding an element to the set that is already there (O(n) expected time to build the set). Ralph Boland --~--~-~--~~~---~--~~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Check divisibility by 3
On Aug 16, 7:29 pm, Ralph Boland rpbol...@gmail.com wrote:
On Aug 14, 1:45 am, richa gupta richa.cs...@gmail.com wrote:
can we check the divisibility of a given number by 3 withoutusing
operators like '/' or '%'.
I want the efficient solution to this problem ..
can someone help ??
--
Richa Gupta
(IT-BHU,India)
If the number is an arbitrarily large binary number then
0) Let X be the input number.
1) Add the binary values of each byte of X. Let result be X.
2) If X 255 goto step 1).
3) Look up the answer in a table or
b1) treat X as a base 16 number and add digits. Let the
result be X.
b2) if X 16 go to step b1.
16 should be 15 here. That is: if X 15 go to step b1.
b3) The original number is divisible by 3 IFF X is
divisible by 3 (X in {0,3,6,9,12,15}).
Note that the rule of 3s and the rule of 9s for decimal numbers is be
being
applied here but for the the number 255 and its factors; that is
3, 5, 15, 17, 51, and 85.
It works for the same reason that the rule of 9's (and its factor
rules; i.e.
rule of 3's) works for decimal numbers.
We could call these rules for base 256 numbers
the rule of 3s base 256, the rule of 5's base 256, the rule of 15's
base 256 etc.
The above algorithm can be modified to use 16 bit numbers or 32 bit
numbers instead of bytes.
For 16 bit numbers for the digit base the method can be applied
to factors of 2^16 -1, that is 3,5,17, and 257.
However step 3 cannot be applied to 17 or 257.
For 32 bit numbers you have the additional factor 2^16 + 1 (and the
numbers in its prime factorization but unfortunately 2^ 16 + 1 is
prime).
It can also be modified to determine if the input number is divisible
by 5,6,7,9,12, 14, or 15.
To do digits 7 or 9 one has to use base 64 digits instead of base
256.
(7 * 9 = 63 = 64 - 1).
I believe divisibility by 13 can also be done but a different
algorithm is needed.
Ralph Boland
Ralph Boland
--~--~-~--~~~---~--~~
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
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Check divisibility by 3
On Aug 14, 1:45 am, richa gupta richa.cs...@gmail.com wrote:
can we check the divisibility of a given number by 3 withoutusing
operators like '/' or '%'.
I want the efficient solution to this problem ..
can someone help ??
--
Richa Gupta
(IT-BHU,India)
If the number is an arbitrarily large binary number then
0) Let X be the input number.
1) Add the binary values of each byte of X. Let result be X.
2) If X 255 goto step 1).
3) Look up the answer in a table or
b1) treat X as a base 16 number and add digits. Let the
result be X.
b2) if X 16 go to step b1.
b3) The original number is divisible by 3 IFF X is
divisible by 3 (X in {0,3,6,9,12,15}).
The above algorithm can be modified to use 16 bit numbers or 32 bit
numbers instead of bytes.
It can also be modified to determine if the input number is divisible
by 5,6,7,9,12, 14, or 15.
I believe divisibility by 13 can also be done but a different
algorithm is needed.
Ralph Boland
--~--~-~--~~~---~--~~
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
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] permuting the elements of an array
I have an array of objects and I need to generate all permutations. e.g. for [1,2,3] I get: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] This problem is actually easy to solve and in fact there is a purely iterative solution. However in my case I also need to solve a variant of this problem. In this variant the array has 2n elements grouped into n groups of two elements where each 2 element pair are equal. For example for array [1,1,2,2] I get: [1,1,2,2] [1,2,1,2] [1,2,2,1] [2,1,1,2] [2,1,2,1] [2,2,1,1] Note that in the first case I get n! permutations whereas in the second case I get (2n)! / 2^n permutations. I want to generate the permutations efficiently. I particular it is unacceptable to generate the (2n)! combinations and then remove the duplicates. I have come up only with complicated ways of doing this but I am hoping someone can post or reference a simpler solution. A solution that generalizes in various ways would be nice but not important to my particular problem. I will be implementing the final solution in Smalltalk (Squeak) and eventually in other languages as part of an implentation of the spine tree decomposition data structure. It will be released (in Squeak at least) under the MIT license. Thanks for any help provided. Ralph Boland --~--~-~--~~~---~--~~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Deciding on a project
On May 28, 8:27 am, Miroslav Balaz gpsla...@googlemail.com wrote: and that polygons are convex? No, the polygon need not be convex, though my algorithm is based upon an algorithm that only works for convex polygons. In fact the polygon need not be simple though what you mean by area and chord for non simple polygons needs to be defined. Of particular interest are overlapping polygons. Overlapping polygons can have multiple horizontal trapezoidizations. In my paper I show that the sum of the areas of the trapezoids of each trapezoidization is the same; an intuitive result perhaps but it's not at all clear how to prove it. My point in all this though is that the algorithm is simple enough for a 15 year old interested in computational geometry to implement. Ralph Boland 2009/5/25 Ralph Boland rpbol...@gmail.com On May 24, 5:05 am, Albert albert.xtheunkno...@gmail.com wrote: Hi, I'm 15 years old and I'm interested in algorithms, data structures, computational geometry and general coding. What sort of projects could I do in my spare time that fuels my interests and is something I can go on with? Other than competing in USACO... Thanks Albert In my Ph.D. thesis is an algorithm that is quite simple yet pretty neat that you might enjoy implementing. My guess is that it is at least 100 times simpler and 100 times faster that the previous best algorithm for polygons of practical size. This level of improvement is possible in part because the previous best algorithm for this problem triangulates the input polygon and my algorithm does not! Though I know of no applications of this algorithm the simplicity of the problem suggests that applications are out there. Who knows, you might be able to sell it. The algorithm involves computing areas of polygons. More precisely, given a polygon P, the algorithm constructs from P a data structure with which, when given a chord C of P, the algorithm can compute the areas of the two subpolygons of P determined by C, say P1 and P2. (In other words the chord C cuts the polygon P into two smaller polygons I call P1 and P2; that is: P = P1 union P2 union C.) The algorithm requires linear time and space to construct the data structure. Then, given any input chord C, the areas of P1 and P2 are computed in constant time. If you are interested I can email you a copy of the paper. Actually you can find it on line by searching for my name or the Canadian Computational Geometry Conference. If you have problems understanding the paper I can help. Good luck whatever you decide. Ralph Boland --~--~-~--~~~---~--~~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Deciding on a project
On May 24, 5:05 am, Albert albert.xtheunkno...@gmail.com wrote: Hi, I'm 15 years old and I'm interested in algorithms, data structures, computational geometry and general coding. What sort of projects could I do in my spare time that fuels my interests and is something I can go on with? Other than competing in USACO... Thanks Albert In my Ph.D. thesis is an algorithm that is quite simple yet pretty neat that you might enjoy implementing. My guess is that it is at least 100 times simpler and 100 times faster that the previous best algorithm for polygons of practical size. This level of improvement is possible in part because the previous best algorithm for this problem triangulates the input polygon and my algorithm does not! Though I know of no applications of this algorithm the simplicity of the problem suggests that applications are out there. Who knows, you might be able to sell it. The algorithm involves computing areas of polygons. More precisely, given a polygon P, the algorithm constructs from P a data structure with which, when given a chord C of P, the algorithm can compute the areas of the two subpolygons of P determined by C, say P1 and P2. (In other words the chord C cuts the polygon P into two smaller polygons I call P1 and P2; that is:P = P1 union P2 union C.) The algorithm requires linear time and space to construct the data structure. Then, given any input chord C, the areas of P1 and P2 are computed in constant time. If you are interested I can email you a copy of the paper. Actually you can find it on line by searching for my name or the Canadian Computational Geometry Conference. If you have problems understanding the paper I can help. Good luck whatever you decide. Ralph Boland --~--~-~--~~~---~--~~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Geometric Algo..
On Nov 20, 1:46 pm, Monty [EMAIL PROTECTED] wrote: Hi Frndz, If there are n points on the circumference of circle(order not known) ,how can we find out the closest pair in complexity O(nlgn)... pls help with the answer... thnx. The closest pair will be the closest pair measured by distance along the circle. Select a start point on the circle and measure distance to each point in one direction around the circle. Now sort. Then add 2pi to each value to create another set of n values (2n in total all sorted). Then find closest pair in O(n) time by comparing consecutive values. If closest pair has first value from first set of points and second value from second pair of points then shorter arc along circle joining points contains start point. Ralph Boland --~--~-~--~~~---~--~~ 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] two solutions looking for problems to solve
I have two nice algorithms (which I will publish when I get the chance) for which I would l like to know if there are important applications outside of those I know if in Computational Geometry. Both algorithms are on polygons. They are: 1) Visibility of objects in a n vertex simple polygon P. Consider that you want to construct a data structure that allows you to in O(1) time: a) Given two vertices or edges of P compute if there is a chord of the polygon that joins them. b) Given any two of a fixed set of points on the boundary of P compute if there is a chord of the polygon joining them. c) Given any two of a fixed set of points in the interior of P compute if there is a line segment interior to P joining them. For a) I have a data structure constructed in O(n log n) time which requires O(n log n) space. These costs are O(n) in best case and the average case is probably good. For b) and c) I have data structures constructed in O((n +k)log(n)) time which requires O((n+k) log(n)) space where k is the number of fixed points. 2) Ray shooting in a n vertex polygon: Construct a data structure that allows one to quickly shoot a ray from inside a polygon and compute the first intersection of the ray with the boundary of the polygon. There already exist 3 optimal algorithms for this problem and my solution is not optimal because the building the data structure requires O(n log n) time (optimal is O(n)) though, like the optimal algorithms, the data structure requires O(n) space and the actual ray shoot is O(log n). The advantages of my algorithm are: a) It is considerably simpler than the other algorithms. b) The constant coefficients for the complexities are lower than the optimal algorithms; thus my algorithm should be faster in practice. I expect this to be true even for the data structure construction step because the worst case O(n log n) construction time scenario is unlikely (I believe). c) The algorithm is new and quite different from the optimal solutions so there may be room for improvement. Perhaps the preprocessing can be reduced to O(n). I hasten to point out that my ray shooting algorithm is still missing a few details so my claims could in the end prove false. If you have knowledge (or ideas) of applications of these algorithms I would appreciate hearing about them. Suggestions of other groups that would be interested in my algorithms would also be appreciated. I am willing to implement these algorithms; if someone would pay me to do so of course. Thanks Ralph Boland [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
