Algorithms

Member 41945936-Nov-08 8:22

6-Nov-08 8:22

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.

⁷³Zeppelin6-Nov-08 8:29

6-Nov-08 8:29

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 well-defined first!

furqan_sindhu9-Nov-08 19:01

furqan_sindhu

9-Nov-08 19:01

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!

Member 419459310-Nov-08 3:08

10-Nov-08 3:08

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 "re-districting" 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 piece-wise efficient solutions to this type of problem described in this book, and Sedgwick explains it so clearly.

Dave.

furqan_sindhu9-Nov-08 18:56

furqan_sindhu

9-Nov-08 18:56

well,

i dont know anything at all. i just have a list of edges and thats all.

I was working on this and uptil now, i have come up with some code that gives me all possible polygons from those edges.
All possible means that it returns those polygons as well that contain multiple small polygons too. I am trying to come up with something to eliminate these bigger polygons Smile | :)

Anyways! i think i will get it done, inshaALLAH.

darrellp28-Nov-08 19:38

darrellp

28-Nov-08 19:38

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.

Random Number Generation

BobInNJ5-Nov-08 13:47

5-Nov-08 13:47

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

⁷³Zeppelin5-Nov-08 21:36

5-Nov-08 21:36

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(1-p^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.

BobInNJ6-Nov-08 6:29

6-Nov-08 6:29

Zeppelin,

Thanks for the response. I am talking about multiple random variables with a given
correlation matrix. I am familar with Cholesky decompostion but not eigenvector decomposition.

Bob

⁷³Zeppelin6-Nov-08 8:28

6-Nov-08 8:28

Cholesky decomposition and eigenvector decomposition will give you the same result for this problem. Since Cholesky is easier to implement, I'd suggest using that method.

The method is just a matrix form of the calculation I described above.

We want U'U = C where C is the correlation matrix. So, assemble your correlation matrix and apply Cholesky decomposition to it. This gives you U. Generate, say, 5 series of random variates of 100 observations. Assemble those 5 column matrices into a large matrix so that the dimension of N is 100x5. This means the correlation matrix has to be 5x5 and contains your known/desired cross-correlations. The 5 correlated series are simply N*U. All done!

Eigenvector decomposition proceeds in a similar fashion but is more complicated to implement. Given the correlation matrix, C, you calculate its eigenvectors and eigenvalues (standard linear algebra). If the eigenvectors are E_i and the eigenvalues are L_i, where i is a subscript, then we calculate a matrix V such that:

V = E_i*diag(sqrt(L_i))

where diag is a diagonal matrix with L_i on the diagonal. Because of it's construction matrix V will have the property that: V'V = C, C being the correlation matrix. Then, as above we have U'U = C where, conveniently (ha!) U = V'.

Nifty, but a roundabout route and used mainly for matrices that have problems being decomposed via Cholesky. Now our correlated random numbers, R_c are just:

R_c = R*U where R is the matrix of original random numbers.

BobInNJ6-Nov-08 9:56

6-Nov-08 9:56

Zeppelin,

When you write U'U = C, is U' the transpose of U? I am thinking that U' should be lower triangular and U should be upper triangular. In addition, U' should have all 1s on its main diagonal. Is this right?

Thanks

Bob

⁷³Zeppelin6-Nov-08 10:21

6-Nov-08 10:21

Yes, sorry. The prime indicates the transpose. U should be upper triangular if C is positive definite, correct. Thus U' will be lower triangular.

Certainly C should have all ones on its main diagonal (and be symmetric) but U may not necessarily have all ones, no.

A quick calculation using the correlation matrix C:

1.0000 0.6000 0.3000
0.6000 1.0000 0.5000
0.3000 0.5000 1.0000

gives U as:

1.0000 0.6000 0.3000
0.0000 0.8000 0.4000
0.0000 0.0000 0.8660

BobInNJ6-Nov-08 12:51

Re: Random Number Generation [modified]

6-Nov-08 12:51

Zepplin,

Your answer makes a lot of sense to me. However, I need to ask a different question. Suppose that I have n random numbers that were generated independently with mean 0 and variance 1. However, I want these numbers to be correlated by a given correlation matrix (this is the same as my original question) in addition I have two vectors u and v. I want the ith number generated to have mean u[i] and variance v[i]. Can I do this by doing the following?
1) Use your above algorithm to generate n correlated random numbers
2) Multiply the ith number by v[i] to give it the correct variance
3) Then add u[i] to the ith number to give it the correct mean.

If I do all this, will I get the distribution of numbers that I seek?

Thanks

Bob

⁷³Zeppelin6-Nov-08 20:50

Records and Clusters [modified]

6-Nov-08 20:50

Yes, this will work. To be perfectly clear, this method will work if the random numbers you are generating are being drawn from a normal/Gaussian distribution with mean 0 and variance 1. Bear in mind that as a result of the law of large numbers[^] you will probably require a large number of samples to get close to the mean and variance that you want. I would suggest a minimum of 1000 samples and go up from there. Also, if you want the variance to be, say, 0.3 then you have to multiply (a normal variable with mean 0 and variance 1) by the square root of 0.3.

To summarize, if U is your Cholesky factor, and X is distributed as a normal variable with mean zero and covariance matrix I (the identity) then:

U*X is distributed as normal with mean zero and covariance matrix C.

Also, if you want a normal variable Z with mean m and covariance matrix C then Z = m + U*X where X is normal with mean 0 and variance-covariance matrix I (the identity). To change the variance of a given column of X, simply multiply that column by the square root of the variance you want to use. Since these are linear transformations, they will also preserve your correlation structure.

modified on Friday, November 7, 2008 2:58 AM

DQNOK5-Nov-08 4:40

5-Nov-08 4:40

For many varied reasons, I decided to write my own balanced binary tree library. One feature of my library that I haven't seen in other freely available libraries is "clusters", and a "recluster" function.

The problem that I am attacking is that as elements are randomly added to the tree, the tree rotations that automatically happen to keep the tree balanced tend to spread the edge pointers all over the place. The end result is that in a large tree, a typical traversal can require reading nodes from all over physical memory (or disk pages): a very inefficient use of cache. By clustering several subtree "near the root nodes" together in physical memory, tree traversals can be sped-up significantly by keeping nodes that always get visited near one another within physical memory (or on the same disk page). For example, in a properly clustered tree, with clusters large enough to hold 4 levels of records (1+2+4+8 = 15 records), a tree of height 16 (>45000 records) can be traversed in only 4 cluster reads instead of 16 reads that might be required of a non-clustered tree.

What I don't know is a good way to measure how "out-of-cluster" a tree is. I'd like to be able to determine when a tree needs to be reclustered. I'm sure there is good theory out there for this; and the idea doesn't seem to be that difficult, but I haven't run onto the solution yet. I've spent a little bit of time googling for a method, and probably a couple of hours thinking about it. Nothing yet.

Any ideas or helpful links?

David
---------
Empirical studies indicate that 20% of the people drink 80% of the beer. With C++ developers, the rule is that 80% of the developers understand at most 20% of the language. It is not the same 20% for different people, so don't count on them to understand each other's code.
http://yosefk.com/c++fqa/picture.html#fqa-6.6
---------

modified on Wednesday, November 5, 2008 11:33 AM

Member 41945935-Nov-08 6:28

5-Nov-08 6:28

Have you ever considered B+ trees as implemented by "The C Database Tool Chest", Mix Software. Mix is still on the web - Google "Mix Software". Note that the term "database" is, in fact, just a B+ tree. The database is a tree of memory or file blocks which contain multiple keys and records.

I got this in '85 and have used it ever since. I got the source software (don't know if this is still available). Not Open Source, but any programs that are released can be used without any royalty, only restriction is that it must be linked into an object, no DLLs, and the neither the source nor the library can be released - only the executable with the embedded code. With the source, you can make any modifications you want.

I modified it (originally 16bit - used Borland C to compile) to now use VS2008 thus 32 bit and supports >4GB files. Major rewrite to unwind the INT usage which now is 32 bit - in 16 bit an INT was 16 bit. Many conflicts with structure layout, and old 16 bit databases couldn't be read with the 32 bit version, nor the other way around. I built my version where I could declare which size of INT I wanted so I had only one converter to work with. I created two converters (16 bit and 32 bit) which could read the appropriate data base (in ascending order) and output a flat file with the data it contained, and then read in the flat file and write the other bit sized database.

Dave.

DQNOK5-Nov-08 6:56

5-Nov-08 6:56

Member 4194593 wrote:
Have you ever considered B+ trees as implemented by "The C Database Tool Chest", Mix Software.

No, I hadn't; but I am familiar with Mix, and have used both their Power C compiler and their C utilities toolchest.

I'll have to back-up and reconsider whether this would be a good approach to my end goal (which was NOT to rewrite the balanced binary tree algorithms).

I originally rolled my own balanced binary tree routines because the ones I found on the web didn't support duplicate keys, nor multi-threading. The clusters were an after-thought (actually, they came about from a "Hey, I can use the tree structure instead of yet-another-roll-my-own exotic structure -- IF I can speed them up sufficiently -- perhaps reclustering would do it).

Thanks for the thoughts.

Member 41945935-Nov-08 7:44

5-Nov-08 7:44

David,

Good that you like David. You be David, I be Dave. Good name.

The blocks in the B+ tree do not exactly correspond to the clusters you use, but do tend to group records together. The interesting thing is that the tree is self leveling. All blocks are identified by a block number. All of the full records are on the bottom level of the tree, linked horizontally by their block numbers, and have an array of offsets in each block to the records, thus constitute an "array", making it easy to go from one record to another. Above the "leaf" nodes at the bottom is an interior node or a layer of interior nodes which only contain the keys (not the additional data) and each key is associated with the block number containing the child nodes below. The first block (block 0) is a header block containing linking info (first leaf block, last leaf block, i.e. first record and last record), and the current root node. Whenever a node (either a leaf node or an interior node)) fills up (not when it is found to be full when a new record needs to be added, but whenever it becomes full due to the addition of a record), it attempts to offload some records to the prior same level block or following same level block, and if that is not possible, the block is split with half of the records in one and the second half in the other and these two blocks are linked. This also creates a new record for the parent block pointing to the block that just split, which may also cause the parent to split, on up the tree until maybe the root block needs to split thus creating a new root and updating the pointer of the header block. The blocks are allocated in memory with a buffer pool which is maintained with an LRU list, and when the buffer pool is full and a new block is needed, the LRU block is written (if dirty) to the database file, randomly by block number, or just discarded and reused if not dirty. Blocks can thus be either in-memory, or else on-file. Blocks are not written to file unless they hit LRU status and a new block is needed, or at the end, when the tree is closed. Multiple trees can be opened at one time (256 of then sharing the buffer pool). I build an application that needed to create a massive tree, then discard it and process other records comprised from the record numbers only. This caused the tree to be written out, then discarded. I wrote a new function to purge a tree without writing by just modifying the header record to indicate that it was empty, writing that out and closing the tree, then returning all buffer pool records to the pool, then discarding the file at the application level. Saved a massive amount of time.

Dave.

DQNOK6-Nov-08 4:54

6-Nov-08 4:54

This discussion has sent me looking into B+trees. Some of the little code I've found looks ridiculously simple (by comparison to my BalBinaryTree implementation). I have no idea of speed comparisons, but it makes sense that they would be fast or else RDBMS's wouldn't use them. Plus it seems they might actually be smaller since every record in my tree system carries 12 bytes of overhead.

Yes, the mix source is still available, but it sounds like the right source to have is Mix's (which of course requires a small $ outlay) plus your modifications.

My (junk) e-mail address is davidlqualls@yahoo.com
I don't check it every day; and it fills up with garbage pretty fast, but if you'll put "B+Tree" in the subject line, I'll be looking for it.

Thanks.

David

Member 41945936-Nov-08 7:57

6-Nov-08 7:57

DQNOK wrote:
which of course requires a small $ outlay

The operative word here is "small" not like VS, and the library an be included in an executable royalty free.

Dave.

Member 419459325-Apr-09 4:28

25-Apr-09 4:28

David,

Sorry this has taken so long to answer. It got buried on my email with Christmas correspondence, and you never responded to this thread again, and I got off on 15 other tangents.

Did you ever get the Mix source? I can't legally send you any "fixed" source unless you have the original source.

How is your balanced tree going?

Dave.

DQNOK27-Apr-09 3:13

27-Apr-09 3:13

Thanks for remembering me.

I looked into it and decided you were right; using the binary tree was the wrong approach. Binary trees just do too much memory thrashing.

I also got off on a really hot project and had to set it aside for a while.

I downloaded a couple of free BTree libraries, but I'm never happy with stuff I get from outside. They will have been developed with their own support libraries, which usually conflict with mine, or they are missing features I want, or are bloated with features I don't want, etc.

I really just wanted an in-memory index, without the burden of a disk-based system. However, I really should consider a product that has disk-based storage in case I want to expand later on.

I'm still interested, just haven't taken "the plunge" yet. It's not the money; it's the time committment in learning a new system and adapting all my stuff to their way of doing things.

I'm just responding to your post without having gone back and reviewed everything that was said to this point. I'm going to do that, plus, if you have anything else new to add, I'd be glad to hear it. Perhaps I should just go ahead and buy the source...

DQNOK27-Apr-09 5:57

27-Apr-09 5:57

A second response:

Have you noticed that Mix now sells a Win32 version of their database toolchest? I don't suppose you've compared their implementation against yours, have you? I know nothing except what they've posted on their web site.

David

Member 419459327-Apr-09 11:22