Fixed-Parameter Algorithms for Optimal Convex Partitions and Other Results
Popular Abstract in Swedish I denna avhandling studerar jag tvådimensionella geometriska optimeringsproblem. Gemensamt för många praktiskt och teoretiskt intressanta problemställningar inom området är att det är mycket svårt att ta fram optimala lösningar. Det tar helt enkelt alltför lång tid att undersöka alla möjligheter för probleminstanser med stora mängder indata då beräkningstiden växer expoIn this thesis I study two-dimensional geometric optimization problems for which it is difficult to find efficient, exact, deterministic algorithms. All known solutions to these problems require time that is exponential in the total size of the input. The work done in this thesis is a contribution to the research directed at attacking and coping with such NP hard problems in computational geometry