

looking for something a leeeeeeeeettle more clever!
Iain.






I owe the inventors of least squares an apology  it is clever. But it is only a method for determining how good a fit your function is to the data  it only indirectly helps you get that function.
There's nothing wrong with good old fashioned stats, but I'm looking for something more along the lines of the nice algorithm for working out a convex hull. One of those "oh, that's neat, and about a million times faster than me throwing brute force PC guesswork at the problem".
Well, maybe I'll invent that cunning method, and retire to a comfy slippered life as a CS professor.
Iain.





Iain Clarke wrote: But it is only a method for determining how good a fit your function is to the data  it only indirectly helps you get that function.
It actually helps to find the parameters of the function, but you should make a 'a priory' (as already pointed out by ^{73}Zeppelin) hypothesis about it. I supposed (wrongly) you were pretty confident it was a Gaussian shape.
Iain Clarke wrote: Well, maybe I'll invent that cunning method, and retire to a comfy slippered life as a CS professor.
Good luck, Prof.Clarke (it sounds good)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
 Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
 Iain Clarke
[My articles]





Try nonparametric kernel density estimation to fit it. That way you don't have to assume a distribution a priori.
Link[^]!





looks promising... just need to change my question to how to do that! (or read more...)
Iain.





Hi Iain,
Kernel density estimation is not as complicated as it sounds. You just need the two functions from the Wikipedia article I linked to. The real problem is the choice of bandwidth, h. You can actually adjust this manually  algorithms for calculating h based on your sample can be more complicated than the density estimation itself. I always adjust h by hand (well, in most cases!).





Well, I'll be writing myself a dialog app with some self generated data later, and I'll see how well I've absorbed that page!
Should wake my brain up at the very least!
Iain.





If you need help, post here. I keep checking this forum.





PLZ SEND CODE. URGENTZ!!!!
Iain.






Dear All,
i have a list of edges like
(0,0),(2,0)
(2,3),(3,4)
(2,0),(2,2)
(0,0),(1,5)
(1,5),(1,10)
(3,4),(3,10)
(2,3),(1,5)
(3,4),(4,0)
(1,10),(3,10)
If you draw these edges on a Cartesian coordinate system, you visually see 3 polygons.
In mapping applications, a polygon is defined by a continuous, closed set of data points. So, output required is a a list like this.
(0,0),(2,0),(2,3),(1,5),(0,0)
(2,0),(4,0),(3,4),(2,3),(2,0)
(2,3)(3,4),(3,10),(1,10),(1,5),(2,3)
Can you please guide me how to????
Simplifying, i need to have Voronoi polygons around my points. Voronoi algorithms gave me the list of edges, but i am unable to get polygons from those edges.
Hope some one can guide!!!





Do you know a priori how many sides each polygon has?
Also, is this an ordered list?






furqan_sindhu wrote: what is meant by ordered list in this case? the list is totally random, just a list of all the edges, no ordering at all.
This is what I was trying to understand when I asked about an ordered list. If all the points are simply in a random list, how can you possibly reconstruct the polygons based only on a list of random points? The problem is that polygons can take on complicated shapes, so you need to know something about number of sides and/or which points should belong to which polygons. At the very minimum, the points should be ordered according to which polygon they belong to. Is there no way of doing this? Can't you create a polygon class that contains a list of points, for example?





You might want to check in "Algorithms" by Robert Sedgewick, published by AddisonWelsley. He has several algorithms, including "Convex Hull" and "Voronoi" for solutions for these problems.
Dave.





I'm not familiar with the book or the algorithms, but I don't think he's trying to construct the convex hull. I think he's got a randomized list of polygon edges for separate polygons and he's trying to reconstruct the component polygons from the list. A convex hull can certainly be determined given the points, but I'm not convinced that's what he wants to do.





My reply was more directed to his statement that he didn't know what to do with his Voronoi edges. In addition, his stated edges do NOT form three polygons. There are two missing edges one between 2,2 and 2,3, and the other between 2,0 and 4,0, both of which he filled in in the case of the polygon descriptions. He is forming a convex hull with enclosed polygons. He also probably wants to split up the polygons into triangles, but that is another topic.
Dave.





So the list isn't even complete? Hmmmm. Methinks he needs to put a little more forethought into this one. It helps to have the problem welldefined first!





oh, i had a look at your message a little late "Member 4194593".
thanks for your reply.
i think i accidentally missed those edges. my apologize!!!
i dont want to construct triangles, rather polygons. i will have a look at those alogs!





I have thought about the problem these last few days. Googled for "Convex Hull" and read all of the related articles. Usually only points are given, not edges. If edges are given, wouldn't at least those edges be required in the final solution? I don't think that eliminating one of these edges would be a solution. If you are given a triangle, then it is a triangle area, you can't make it a square by combining it with some other area  people don't take kindly to "redistricting" or "Gerrymandering".
Fortunately, it has been proven that you only need 4 colors to tint your map when you get it done.
I would be interested in the exact phrasing of the problem as given, along with your final solution. I love algorithms and I frequent these halls daily.
I am serious about the book "Algorithms"  there is such an abundance of simple piecewise efficient solutions to this type of problem described in this book, and Sedgwick explains it so clearly.
Dave.






I think you have some errors in the list of edges. For instance, your polygons include an edge from (2,0) to (2,3) but there is no such edge in your list of edges. Anyway, I think what you're suggesting here is that you've got a list of edges and vertices which define a mesh (often referred to a "boundary representation") and you want to find the polygons in that mesh. I'd suggest that you look at Winged Edge representation, turn your edges into a winged edge rep and get your polys from that. Essentially, you'd have to keep a list of vertices with the edges around them in clockwise order, then traverse each vertex and trace out each poly between adjacent edges. You have to be careful about skipping over polys that have already been listed which means you have to keep track of the polygons each edge separates. It'd be a bit ugly, but I think that's pretty much what's required. It would also mean that the area surrounding the entire mesh will be represented as a "polygon". You can recognize that polygon by looking at the rightmost vertex, getting the first edge from it that is CCW from vertical and the flagging the polygon clockwise from that edge as the "exterior polygon".
If you're looking for a Voronoi diagram that keeps a record of all the polygons, I've got one that I've been thinking about putting up on CodeProject. There's a fortune algorithm already out there on CodeProject, but it has some bugs and pretty much has a dump of edges like you're talking about without an indication of the polygons each edge goes with. Mine gives a full winged edge representation of the diagram which includes all the polygons, edges and vertices with them all hooked together intelligently. If that's what you're looking for, perhaps I'll put my fortune algorithm up earlier rather than later.





I have n random variables. Each random variable is normally distributed with mean 0 and variance 1. In addition, I have a function which I can call which will return a normally distributed random value with mean 0 and variance 1. For each pair of variables, I have their correlation. I would like to generate a list of n random values (one for each of the n variables) such that the given correlations apply. What algorithm should I use to do this?
Thanks
Bob





Do you mean a single random variable with a fixed autocorrelation structure, or are you taking about multiple random variables with a given correlation matrix?
In any event, there are two main ways of doing this; either by Cholesky decomposition or eigenvector decomposition. Cholesky decomposition is probably more conceptually simple.
For normal variables, the basic idea is to find a matrix U such that U'U = C (where U' is the transpose of U) and C is the given correlation matrix. You can then generate correlated random numbers, N' from random numbers N by multiplying by U. That is:
N' = NU
So, how to find U? Like I said, either by Cholesky decomposition or eigenvector decomposition. Until I know what you really want to do, I'll give you the case for pairs of r.v.'s.
For pairs of normal variables, you can generate two sequences of normal r.v.'s, say X1 and X2. Given correlation, p, the new sequence, Y is calculated as:
Y = p*X1 + sqrt(1p^2) * X2
This will give you a sequence Y that has correlation p with sequence X1. If you want a fixed correlation structure between more than two sequences, we'll have to get into matrix calculations.




