عنوان

Some combinatorial optimization problems in computational geometry

شماره

TLpq303958863

زبان متن نوشتاري يا گفتاري و مانند آن

انگلیسی

عنوان اصلي

Some combinatorial optimization problems in computational geometry

نام عام مواد

[Thesis]

نام نخستين پديدآور

M. H. Alsuwaiyel

نام ساير پديدآوران

D. T. Lee

نام ناشر، پخش کننده و غيره

Northwestern University

تاریخ نشرو بخش و غیره

1991

نام خاص و کميت اثر

114

جزئيات پايان نامه و نوع درجه آن

Ph.D.

کسي که مدرک را اعطا کرده

Northwestern University

امتياز متن

1991

متن يادداشت

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

نام الکترونيکي

فرمت انتشار

p

نوع ماده

[Thesis]

کد کاربرگه

276903

سطح دسترسي

a

تكميل شده

Y