Name
Title | ||
|---|---|---|
Centroidal power diagrams with capacity constraints: computation, applications, and extension. |
Abstract | ||
|---|---|---|
This article presents a new method to optimally partition a geometric domain with capacity constraints on the partitioned regions. It is an important problem in many fields, ranging from engineering to economics. It is known that a capacity-constrained partition can be obtained as a power diagram with the squared L2 metric. We present a method with super-linear convergence for computing optimal partition with capacity constraints that outperforms the state-of-the-art in an order of magnitude. We demonstrate the efficiency of our method in the context of three different applications in computer graphics and geometric processing: displacement interpolation of function distribution, blue-noise point sampling, and optimal convex decomposition of 2D domains. Furthermore, the proposed method is extended to capacity-constrained optimal partition with respect to general cost functions beyond the squared Euclidean distance. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2980179.2982428 | ACM Trans. Graph. |
Keywords | Field | DocType |
centroidal power diagram,displacement interpolation,convex decomposition,blue noise | Convergence (routing),Power diagram,Mathematical optimization,Colors of noise,Square (algebra),Computer science,Interpolation,Partition (number theory),Computer graphics,Computation | Journal |
Volume | Issue | ISSN |
35 | 6 | 0730-0301 |
Citations | PageRank | References |
9 | 0.51 | 42 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shi-Qing Xin | 1 | 97 | 13.42 |
| Bruno Lévy | 2 | 2520 | 130.17 |
| Zhonggui Chen | 3 | 78 | 8.93 |
| Chu Lei | 4 | 9 | 5.25 |
| Yaohui Yu | 5 | 9 | 0.51 |
| Changhe Tu | 6 | 288 | 34.47 |
| Wenping Wang | 7 | 2491 | 176.19 |