On a Class of 3SUM-HARD problems in Computational Geometry

On a Class of 3SUM-HARD problems in Computational Geometry
Автор
 
Год
 
Страниц
 
76
ISBN
 
9783639158373
Категория
 
Новые поступления

Описание:

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.

Похожие книги

Mac OS X Version 10.2 Jaguar Little Black BookMac OS X Version 10.2 Jaguar Little Black Book
Автор: Gene Steinberg
Год: 2004
Trade Options Online (Trading for a Living)Trade Options Online (Trading for a Living)
Автор: George A. Fontanills
Год: 2009
Spatial and Spatiotemporal Econometrics, Volume 18 (Advances in Econometrics)Spatial and Spatiotemporal Econometrics, Volume 18 (Advances in Econometrics)
Автор: Edited by Victor Nee & Richard Swedberg
Год: 2004
Cephalic indexCephalic index
Год: 2011
Generalized, Linear, and Mixed Models (Wiley Series in Probability and Statistics)Generalized, Linear, and Mixed Models (Wiley Series in Probability and Statistics)
Автор: Charles E. McCulloch, Shayle R. Searle
Год: 2001