عنوان

Some combinatorial optimization problems in computational geometry

Number

TLpq303958863

.Language of Text, Soundtrack etc

انگلیسی

Title Proper

Some combinatorial optimization problems in computational geometry

General Material Designation

[Thesis]

First Statement of Responsibility

M. H. Alsuwaiyel

Subsequent Statement of Responsibility

D. T. Lee

Name of Publisher, Distributor, etc.

Northwestern University

Date of Publication, Distribution, etc.

1991

Specific Material Designation and Extent of Item

114

Dissertation or thesis details and type of degree

Ph.D.

Body granting the degree

Northwestern University

Text preceding or following the note

1991

Text of Note

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.

Applied sciences

Computer science

geometry

D. T. Lee

M. H. Alsuwaiyel

Electronic name

p

[Thesis]

276903

a

Y