On the Computational Complexity of Partitioning …

CCCG 2014, Halifax, Nova Scotia, August 11 13, 2014. On the Computational Complexity of Partitioning weighted Points into a Grid of Quadrilaterals Alexander Idelberger Maciej Li skiewicz . Abstract equal to the corresponding desired value. If such a Partitioning does not exist, a solution minimizing some In the paper the Computational Complexity of the follow- objective function is required. To express the initial ing Partitioning problem is studied: Given a rectangle Partitioning problem in this setting,Pone needs to define R in the plane, a set Q of positive- weighted points in each reference value equal to n11 n2 q Q (q), where . R, and two positive integers n1 , n2 , find a Partitioning denotes the weight function. of R into quadrilaterals whose dual graph is an n1 n2 The above problem is a natural generalization of the grid such that each quadrilateral contains points of equal well-studied 1-dimensional case: given a set of m positive- total weight.

CCCG 2014, Halifax, Nova Scotia, August 11{13, 2014 On the Computational Complexity of Partitioning Weighted Points into a Grid of Quadrilaterals

Tags:

  Computational, Partitioning, The computational complexity of partitioning, Complexity, The computational complexity of partitioning weighted, Weighted

Information

Related search queries