On a Class of 3SUM-HARD problems in Computational Geometry | Cutting a polygon with a line

Ervin Ruci

ISBN 10: 3639158377 / ISBN 13: 9783639158373

Published by VDM Verlag Dr. Müller, 2009

About this Item

On a Class of 3SUM-HARD problems in Computational Geometry | Cutting a polygon with a line | Ervin Ruci | Taschenbuch | Englisch | VDM Verlag Dr. Müller | EAN 9783639158373 | Verantwortliche Person für die EU: VDM Verlag Dr. Müller, Brivibas Gatve 197, 1039 RIGA, LETTLAND, customerservice[at]vdm-vsg[dot]de | Anbieter: preigu.

Seller Inventory # 101563316

Bibliographic Details

• Title: On a Class of 3SUM-HARD problems in Computational Geometry | Cutting a polygon with a line
• Publisher: VDM Verlag Dr. Müller
• Publication Date: 2009
• Language: English
• ISBN 10: 3639158377
• ISBN 13: 9783639158373
• Binding: Taschenbuch
• Condition: Neu
• Dimensions: 5W x 150H x 220D millimeters 5 millimeters width by 150 millimeters height by 220 millimeters depth
• Weight: 119 grams
• Seller catalogs:
  • Bücher

About this title

Synopsis

Given a simple polygon P and an integer K > 1, we want to compute the set of straight lines in the Cartesian plane that cut this polygon into exactly K simple polygons. We call this set of lines a K-separator and call this problem the K-separator problem. We present an algorithm that finds the K-separators of an n-vertex simple polygon, for all K > 0, in O(n2) total time. We prove that the decision problem given an integer K > 2 and an edge of the polygon, is there a line through this edge that cuts the polygon in exactly K pieces?, is 3SUM-HARD. For the special case when K = 2, we show that the decision problem can be solved in O(n log(n)) time. Several other complexity results may be obtained. We suspect that the problem of finding the cell of maximum depth is also 3SUM-hard, and as a corollary the problem of identifying the line that cuts the polygon in the maximum possible number of pieces is also 3SUM-hard.

About the Author

Born in Vlore, Albania where he lived until the age of 18, went abroad to study (Applied Math, Mount Allison University; Computational Geometry, Carleton University) and work (MTA, CIRA). Is now back in Vlore, teaching at the University of Vlora.