| Abstract
|
:
|
Visibility problems in computational geometry have received considerable attention in recent years due to not only their theoretical beauty, but also their wide range of applications in many areas of the real world, e.g., computer graphics, pattern recognition, robotics, etc. Recently, more visibility problems characterized as an "optimization" problems, have been of interest. In chapter 2 of this dissertation we study the following problem: Given a simple polygon, find a shortest line segment L inside P such that each point inside P is visible from at least one point on L; we will propose a simple algorithm for this problem that runs in O(n log n) time and O(n) space. In chapter 3, we prove the following problem to be NP-hard: Given a simple polygon P, find a polygonal path usd\piusd inside P which is composed of a minimum number of line segments with the property that each point inside P is visible from at least one point on usd\piusd. We also prove two other combinatorial optimization problems in this field to be NP-hard as well: Given a simple polygon P, a subset S of its vertices (edges), find a polygonal path inside P of minimum link-length that visits each vertex (edge) exactly once. In chapter 4, we investigate a new packing problem that is related to computational geometry: Given a large bin of sides X and Y, compute the maximum number of rectangles of fixed sides u and v that can be packed inside the bin with u parallel to either X or Y and no two of them overlap. It is our conjecture that this problem is unlikely to have a polynomial time solution. Hence, we propose a heuristic to solve this problem that guarantees packing at least usd3\over4usd of the number of optimal rectangles. We also show that this bound happens only when u and v are comparable in size to X and Y. Otherwise, the algorithm performance is very reasonable.
|