Some positive and negative results in computational geometry.

摘要

n this thesis we provide improved upper bounds (positive results) and lower bounds (negative results) for some problems arising in Computational Geometry.;One set of results pertains to special types of illumination problems, where the goal is to use conical floodlights positioned at fixed points and rotate them appropriately so that a given region is illuminated. When the target region is a general semi-algebraic set, the problem can be solved in exponential time. We study a special planar case and show that it is in NP. We give a lower bound of ;We also consider the old problem of sorting the x-coordinates of the vertices in a line arrangement. Using previous results we provide a separation between the complexity of the problem for line and pseudo-line arrangements. In addition we provide a new algorithm for sorting cartesian sums with only