A Wonderful Find: My Demise

I've been working on a certain computational geometry problem for about 9 months now. I hoped to make this into my thesis subject, focusing primarily on the algorithm that is necessary for the n-dimensional spatial cache to work. I had not been able to find any papers specific to my problem. I found out tonight that it was because I was searching for the wrong words.

Apparently, there is a 16-year old algorithm for what's called Minimum Partitioning Simple Rectilinear Polygons [IEEE link]. Also, this algorithm runs in O(n log log n), which is very good for an optimal solution. My algorithm was linear, but flawed. It would not minimize, but would run quickly. However, the minimal part was very important.

As I read the papers that use this algorithm (a lot of recent papers have been using this algorithm for designing path-finding algorithms over rectilinear areas), I find that a lot of my assumptions and findings were well founded, and proved 20 years ago. Now, I have proof that my statements are true.

This recent discovery both excites and frightens me. First, I'm excited that I have found an algorithm that will accomplish this goal properly. Now I can write a high-quality implementation paper. The problem is, I wanted to write a theory paper. I want to "discover" and algorithm, or improve upon it. One bright side is: this algorithm is specific to 2 dimensions. I need something for at least 3, and hopefully n, dimensions. If I can take this algorithm, and extend it's speed into further dimensions, with a few tweaks to this specific problem, while battling the exponential complexity brought by the increased dimension, I may have a worthy paper afterall.

I need to work hard during the semester (a fun spring break, perhaps) to get my Thesis as well written and mathematically proven before I get back to work this summer. I'll need all the time I can get to implement this, so I'll need to do most of my writing beforehand.

I still fear that I will have to make this a simple implementation paper, try to get published in a small conference (instead of a journal: my dream come true), and plead one of the theory guys or the math department to let me sneak a thesis in as support research in that field.