Thesis: upper sets in partially ordered sets

Today I finally finished my thesis. It’s topic was to count the number of upper sets in partially ordered sets Which is quite a hard problem since it’s in the complexity class #P-Complete (that’s the class of counting the solutions to the decision problems in NP-complete). All and all I’m quite pleased with the result. Although the upper bound is still O(2^{n}), (can’t quite get under there without solving P=NP and winning a million dollars) I’ve manged to find a solution that has a best case of O(n) both in time and memory complexity. With a particularly large data set the brute-force algorithm took over 2 hours to complete while my algorithm took 0.025 seconds. Now that’s what I’d call a speed gain (and yes it was a real life data set, no tricks here). You can see this for yourself in the graph at the bottom of this post the ‘naïeve algoritme’ is the brute force approach, the ‘Familiealgoritme zonder uptrie’ is the first version of my algorithm, the ‘Familiealgoritme met uptrie’ is the final version of my algorithm. It uses a trie like data structure to speed up searching and uses a lot less memory. Note that the graph has a logarithmic scale.

Unfortunately for most readers my thesis is in Dutch, but I’ve translated the abstract to English:

Counting the number of upper sets in partially ordered sets gives us a unique number that can be used to compare sets. This number is like the fingerprint of a set. Until now there isn’t, as to my knowledge, an efficient algorithm to calculate this number. This meant that the number had to be calculated either by hand or by using a brute force approach. Using a brute force approach leads quickly to problems, even for trivially small data sets since this means that you have to generate 2^n subsets and check each of these subsets on upwards closure. When calculating by hand you can use symmetry but this menial process can take a lot of time and is error prone. In this thesis I present an algorithm that can calculate exact, and usually fast, the number of upper sets in a partially ordered set.

You can download my thesis here: Upper sets in partially ordered sets (Bsc thesis Roy Triesscheijn) as I’ve said before the text is in Dutch, but the proofs and attached code should be readable enough. If you’ve got any questions feel free to ask below!

Thesis time benchmark

Getting the Left, Forward and Back vectors from a View Matrix directly

I was wondering why I had to calculate the forward and left vectors for my arcball camera manually and why these results differed from ViewMatrix.Left and the likes.  So I asked at the xna forums and almost immediately Jeremy Walsh pointed me in the right direction.  He pointed out to me that view matrices are transposed from a normal matrix (meaning that the rows and columns are switched). To get the right vectors from the view matrix, we have to transpose it again to get the original matrix, however this generates a lot of garbage, so he told me that its better to construct the vectors from the matrix cells themselves.

And so I did, and I’ve packaged them into my neat PositionalMath class (which I might release some day). Here are the methods to get all the information you want from those view matrices, without having to calculate the forward (lookat – position) and crossing that.

// Because a ViewMatrix is an inverse transposed matrix, viewMatrix.Left is not the real left
        // These methods returns the real .Left, .Right, .Up, .Down, .Forward, .Backward
        // See: http://forums.xna.com/forums/t/48799.aspx        
        
        public static Vector3 ViewMatrixLeft(Matrix viewMatrix)
        {
            return -ViewMatrixRight(viewMatrix);
        }

        public static Vector3 ViewMatrixRight(Matrix viewMatrix)
        {
            return new Vector3(viewMatrix.M11, viewMatrix.M21, viewMatrix.M31);
        }
        
        public static Vector3 ViewMatrixUp(Matrix viewMatrix)
        {
            return new Vector3(viewMatrix.M12, viewMatrix.M22, viewMatrix.M33);
        }

        public static Vector3 ViewMatrixDown(Matrix viewMatrix)
        {
            return -ViewMatrixUp(viewMatrix);
        }

        public static Vector3 ViewMatrixForward(Matrix viewMatrix)
        {
            return -ViewMatrixBackward(viewMatrix);
        }

        public static Vector3 ViewMatrixBackward(Matrix viewMatrix)
        {
            return new Vector3(viewMatrix.M13, viewMatrix.M23, viewMatrix.M33);
        }
04
Mar 2010
CATEGORY

Blog

COMMENTS 2 Comments