Some positive and negative results in computational geometry |
Posted on:1995-10-26 | Degree:Ph.D | Type:Thesis |
University:Rutgers The State University of New Jersey - New Brunswick | Candidate:Streinu, Ileana | Full Text:PDF |
GTID:2478390014990257 | Subject:Computer Science |
Abstract/Summary: | |
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... |
Keywords/Search Tags: | Results, Provide, Problem |
|
Related items |