Pith. sign in

REVIEW 2 major objections 6 minor 47 references

Planar p-center problems are solvable in polynomial time when clustering a Pareto Front

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read Planar K-center clustering, NP-hard in general, is solvable in polynomial time for two-dimensional Pareto fronts via a dynamic program that cuts the front into contiguous blocks.

desk verdict The paper has a credible DP design and improved complexity bounds for p-center on 2D Pareto fronts, but the proof of the load-bearing interval-optimality lemma has a false containment and needs a real fix before the main theorem is supported. read the letter →

arxiv 1908.09648 v1 pith:42AKTFYS submitted 2019-08-19 cs.CG cs.CCcs.DMcs.DS

classification cs.CGcs.CCcs.DMcs.DS MSC 68U0590C2790C39
keywords ParetofrontK-centerproblemp-centerdynamicprogrammingcomputationalgeometrybi-objectiveoptimizationclusteringpolynomial-timealgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that the planar K-center clustering problem, which is NP-hard in general, becomes solvable in polynomial time when the input points form a two-dimensional Pareto front: a set of pairwise incomparable points in the plane, such as the nondominated solutions of a bi-objective optimization problem. The paper argues that after sorting the front by one objective, an optimal clustering can be assumed to cut the front into contiguous index blocks, and that each block's covering radius is then easy to evaluate. This yields a dynamic programming algorithm running in $O(KN\log N)$ time and $O(N)$ memory for the continuous K-center problem, and in $O(KN\log^2 N)$ time for the discrete K-center problem when $K\ge 3$, with the discrete 2-center case in $O(N\log N)$. A sympathetic reader will care because bi-objective solvers routinely output huge fronts, and a fast exact clustering method turns such a front into a small set of representative balls for decision making.

What carries the argument

The load-bearing object is the interval property induced by the Pareto order. Because any two points of a 2D Pareto front are comparable in the sense $x_i \prec x_j$ when both coordinates order oppositely, sorting by one objective totally orders the front, and Euclidean distances from either endpoint grow monotonically along the order. This makes the cost of a cluster depend only on its extreme indices—for the continuous 1-center, exactly half the distance between the extremes—and it lets the paper restrict dynamic programming to clusters that are contiguous index intervals. Inside each DP line, the cost as a function of the split point is first decreasing then increasing (unimodal), so a binary search finds each $C_{i,k}$ in $O(\log i)$ cost evaluations; a memory-efficient backtracking pass then recovers an optimal partition in $O(N\log N)$ time.

What would settle it

Take a small random 2D Pareto front (for example $N=8$, $K=3$), compute the exact discrete K-center optimum by exhaustive enumeration of all partitions, and compare it with the DP restricted to interval clusters; any instance where the interval optimum is strictly larger would disprove Proposition 3 and break Theorem 1 for the discrete case.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: for a set $E=\{x_1,\ldots,x_N\}$ of pairwise Pareto-incomparable points in $\mathbb{R}^2$, both the continuous and discrete K-center problems—cover the points with K equal-radius disks, with centers anywhere or restricted to the point set, minimizing the radius—admit exact polynomial-time solutions. The mechanism is Proposition 3, which states that there exists an optimal solution whose clusters are intervals $C_{i,i'} = \{x_j : i\le j\le i'\}$ in the total order induced by sorting on the first coordinate. With interval clusters, the recurrence $C_{i,k} = \min_j \max(C_{j-1,k-1}, f^\gamma(C_{j,i}))$ computes optimal values by dynamic programming; each line of the DP table is computed by logarithmic dichotomic search, because the objective is unimodal in $j$. The stated complexities are $O(KN\log N)$ time and $O(N)$ space for the continuous case, and $O(KN\log^2 N)$ time and $O(N)$ space for the discrete case with $K\ge 3$, with special cases $O(N)$ for 1-center and $O(N\log N)$ for discrete 2-center.

Load-bearing premise

The whole algorithm stands on Proposition 3, which says that after sorting, some optimal clustering uses only contiguous index blocks; the proof of that proposition in Section 4.3 contains a step where the final block is treated as a subset of the original final cluster when it is actually a superset, so an additional geometric argument is needed to justify the interval property in the discrete case.

Editorial extensions

If this is right

  • Bi-objective optimizers can replace heuristic archiving of nondominated solutions with exact K-center summaries, giving a provably smallest covering radius for any chosen K.
  • The same DP handles continuous and discrete variants, so users can choose between arbitrary centers and centers restricted to the front without reimplementing the algorithm.
  • The $O(N)$ memory footprint and near-linear per-K costs make repeated runs for different K practical for elbow analysis of the optimal radius.
  • Special cases improve on general planar bounds: 1-center in $O(N)$, discrete 2-center in $O(N\log N)$, and continuous 2-center in $O(N\log N)$.
  • Computing all k-center values up to a bound $K'$ costs $O(NK'\log^{1+\gamma}N)$, which keeps the DP useful for sweeping K when the user does not know the right number of clusters in advance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • This structure suggests the same DP should extend to other geometries whose cluster cost depends only on the extreme points, such as the $L_\infty$ norm; random-front experiments would confirm the extension.
  • Because each line of the DP table is independent once the previous line is known, the $O(N)$-space version should parallelize well on GPUs, with the biggest wall-clock gain in the discrete $\log^2 N$ case.
  • For a decision-maker, the near-linear runtime would make the elbow curve of optimal radius versus $K$ interactive even for large fronts, an operational use the paper mentions only briefly.
  • The gap between the continuous and discrete bounds comes entirely from computing each discrete cluster cost by binary search over candidate centers, so a faster discrete cluster-cost data structure would immediately sharpen the discrete complexity.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper considers the continuous and discrete K-center clustering problems for a set E of N points in R^2 that are pairwise incomparable under Pareto dominance (a 2D Pareto front). It claims that both problems are solvable in polynomial time, with O(KN log N) time and O(N) space for the continuous case (K >= 2), and O(KN log^2 N) time and O(N) space for the discrete case (K >= 3), with special cases for 1-center and 2-center. The algorithmic core is a dynamic program (Section 5, Eq. (18)) whose validity rests on Proposition 3, a structural result asserting that there exists an optimal partition in which every cluster is a contiguous index interval C_{i,i'} = {x_j : i <= j <= i'}.

Significance. If the main result is correct, it is a significant contribution: planar p-center problems are NP-hard in general, and identifying the Pareto-front restriction as a polynomially solvable class is both natural and useful for multi-objective optimization applications. The proposed unified DP has attractive near-linear running times and linear memory. However, the central structural claim (Proposition 3) is not proved as written, and the correctness of the DP is exactly contingent on that claim. The paper does provide useful intermediate observations (e.g., O(1) continuous cluster costs via extremes, O(log n) discrete cluster costs) and a plausible algorithmic framework, but the current proof gap must be resolved before the main theorem can be accepted.

major comments (2)
  1. [Section 4.3, Proposition 3] The proof of Proposition 3 contains a false containment. It defines C'_K = {x_j : i <= j <= N} and asserts "for all k, C'_k ⊂ C_k" to conclude via Lemma 5 that f_gamma(C'_k) <= f_gamma(C_k) <= OPT. For k = K, however, C'_K is a superset of C_K, not a subset, because C_K is the cluster containing x_N and i is the smallest index in C_K, but C'_K includes every Pareto point with index between i and N, including points that may belong to other clusters. Lemma 5 gives f(C'_K) >= f(C_K), so the needed bound f(C'_K) <= OPT does not follow. Since the DP recurrence in Section 5, Eq. (18), restricts attention to interval clusters and is justified solely by Proposition 3, the central polynomial-time claim is not established by the proof as written. The interval property may be true and recoverable by a different exchange or induction argument, but no such argument is supplied. This is a load-bearing gap, not a cosmetic issue.
  2. [Section 6.2] The paper remarks that "Many optimal solutions may be nested, i.e. non verifying the Proposition 3." This does not contradict Proposition 3, which only asserts existence of at least one optimal interval solution. But it underscores that the proof must construct such a solution without relying on the false containment. The current proof does not do so, and the remark does not repair the derivation.
minor comments (6)
  1. [Section 4.3, Proposition 3 proof] The text writes "f_gamma(C'_k) ⊂ f_gamma(C_k)"; the subset symbol should be the inequality "<=".
  2. [Section 5.2, Proposition 5] The statement "O(log^gamma i)" is inconsistent with the surrounding analysis; it should be "O(log^{1+gamma} i)" (i.e., O(log i) for continuous, O(log^2 i) for discrete), matching the complexity proof of Theorem 1.
  3. [Algorithm 1 (Section 4.4)] In the line "Compute idMid = floor((i+i')/2)", the midpoint should be computed from the current search bounds idInf and idSup, not from the original endpoints i and i'. As printed, the dichotomic search would not narrow correctly.
  4. [Algorithm 4 (Section 5.3)] The while loop contains "minId = minId", which is an infinite loop. Presumably the intent is to decrement minId (minId <- minId - 1) or similar; without this fix, Algorithm 4 does not terminate and Proposition 6 is unsupported.
  5. [Appendix A, Lemma 10 proof] After translating the origin to the midpoint x_0 = (x_i + x_j)/2, the coordinates of x_0 should be (0,0), not (1/2 sqrt(2) diam, 1/2 sqrt(2) diam). The proof of equation (21) needs to be reworked; the conclusion of Lemma 3 is standard, but the proof as printed is garbled.
  6. [Appendix A, Lemma 6 proof] The proof refers to "Proposition 2" when it means "Lemma 2" (the monotonic distance lemma).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the parameter-free DP derivation is self-contained; the false-containment issue in Proposition 3 is a proof gap, not a reduction of the result to its own inputs.

full rationale

The paper's central claim is that planar p-center clustering on a 2D Pareto front is polynomial-time solvable via a dynamic program over contiguous index intervals. No parameter is fitted and then renamed as a prediction; the cluster-cost formulas in Lemmas 3 and 4 are derived from the hypotheses, and the DP recurrence in Equation (18) is a direct consequence of the stated definitions. The only potentially load-bearing appeal to prior work is to the authors' earlier clustering papers [14,15,16], but those citations are used for context and comparison, not to prove the new complexity theorem. The induction in Proposition 3 does contain a genuine mathematical error: the text asserts C'_k subset C_k for all k, but for k=K the constructed interval C'_K is a superset of the original cluster C_K, so the inequality f(C'_K) <= OPT is not established by Lemma 5 as written. That is a correctness and proof-completeness defect that weakens the justification of the interval-clustering property, but it is not a circularity: the paper does not define its conclusion into its assumptions, does not fit a parameter to the target quantity, and does not import its central claim from a self-citation. Since no circular step can be exhibited under the required standard, the appropriate circularity finding is 0, with the proof gap flagged separately as a correctness risk rather than as circular reasoning.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or fitted constants appear; the entire result is a theorem over Euclidean geometry under the PF antichain assumption. The only invented entity is the '2D Pareto front' ordering, which is a domain assumption, not a physical object.

assumptions (4)
  • domain assumption All points in E are pairwise Pareto-incomparable, so ordering by first coordinate implies the second coordinate is strictly decreasing.
    This is the defining assumption of a 2D Pareto front; it creates the chain structure used by all lemmas.
  • standard math Euclidean distance in R2 and the triangle inequality hold.
    Background geometry; used in Lemma 2 and Lemma 10.
  • standard math Cluster cost is monotone under inclusion of point sets.
    Lemma 5 derives this from the geometry; it is used throughout the DP correctness proof.
  • domain assumption Discrete centers must be chosen among the points of the cluster.
    This is the definition of the discrete p-center variant, not a derived fact.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Planar p-center problems are solvable in polynomial time when clustering a Pareto Front." pith.science (2026). https://pith.science/paper/42AKTFYS

@misc{pith2026190809648,
  author       = {Pith},
  title        = {Pith review of: Planar p-center problems are solvable in polynomial time when clustering a Pareto Front},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/42AKTFYS}},
  note         = {Machine review of arXiv:1908.09648}
}
abstract

This paper is motivated by real-life applications of bi-objective optimization. Having many non dominated solutions, one wishes to cluster the Pareto front using Euclidian distances. The p-center problems, both in the discrete and continuous versions, are proven solvable in polynomial time with a common dynamic programming algorithm. Having $N$ points to partition in $K\geqslant 3$ clusters, the complexity is proven in $O(KN\log N)$ (resp $O(KN\log^2 N)$) time and $O(KN)$ memory space for the continuous (resp discrete) $K$-center problem. $2$-center problems have complexities in $O(N\log N)$. To speed-up the algorithm, parallelization issues are discussed. A posteriori, these results allow an application inside multi-objective heuristics to archive partial Pareto Fronts.

Figures

Figures reproduced from arXiv: 1908.09648 by the authors.

Figure 1
Figure 1. Pareto dominance and incomparability cadrans minimizing two [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Illustration of a 2d PF with 15 points and the indexation implied [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 45 canonical work pages

  1. [1]

    Agarwal and C

    P. Agarwal and C. Procopiuc. Exact and approximation alg orithms for clustering. Algo- rithmica, 33(2):201–226, 2002

  2. [2]

    Agarwal, M

    P. Agarwal, M. Sharir, and E. W elzl. The discrete 2-cente r problem. Discrete & Com- putational Geometry , 20(3):287–305, 1998

  3. [3]

    Auger, J

    A. Auger, J. Bader, D. Brockhoff, and E. Zitzler. Investig ating and exploiting the bias of the weighted hypervolume to articulate user preferences . In Proceedings of GECCO 2009, pages 563–570. ACM, 2009

  4. [4]

    Computing k-Centers On a Line

    P. Brass, C. Knauer, H. Na, C. Shin, and A. Vigneron. Compu ting k-centers on a line. arXiv preprint arXiv:0902.3282 , 2009

  5. [5]

    Bringmann, S

    K. Bringmann, S. Cabello, and M. Emmerich. Maximum volum e subset selection for anchored boxes. arXiv preprint arXiv:1803.00849 , 2018

  6. [6]

    Bringmann, T

    K. Bringmann, T. Friedrich, and P. Klitzke. Two-dimensi onal subset selection for hy- pervolume and epsilon-indicator. In Annual Conference on Genetic and Evolutionary Computation, pages 589–596. ACM, 2014

  7. [7]

    Calik, M

    H. Calik, M. Labb´ e, and H. Yaman. p-center problems. In Location science, pages 79–92. Springer, 2015

  8. [8]

    Calik and B

    H. Calik and B. Tansel. Double bound method for solving th e p-center location problem. Computers & operations research , 40(12):2991–2999, 2013

Show all 47 references
  1. [9]

    Callaghan, S

    B. Callaghan, S. Salhi, and G. Nagy. Speeding up the optim al method of Drezner for the p-centre problem in the plane. European Journal of Operational Research , 257(3):722– 734, 2017

  2. [10]

    Network and discrete location: models, algorithms and appl ications

    M Daskin. Network and discrete location: models, algorithms and appl ications. Wiley, 1995

  3. [11]

    The p-centre problemheuristic and optima l algorithms

    Zvi Drezner. The p-centre problemheuristic and optima l algorithms. Journal of the Operational Research Society, 35(8):741–748, 1984

  4. [12]

    On the rectangular p-center problem

    Zvi Drezner. On the rectangular p-center problem. Naval Research Logistics (NRL) , 34(2):229–234, 1987

  5. [13]

    N. Dupin. Mod´ elisation et r´ esolution de grands probl` emes stochastiques combinatoires: application ` a la gestion de production d’´ electricit´ e. PhD thesis, Univ. Lille 1, 2015

  6. [14]

    Dupin, F

    N. Dupin, F. Nielsen, and E. Talbi. Dynamic programming heuristic for k-means cluster- ing among a 2-dimensional pareto frontier. 7th International Conference on Metaheuris- tics and Nature Inspired Computing , pages 1–8, 2018. 16

  7. [15]

    Dupin, F

    N. Dupin, F. Nielsen, and E. Talbi. k-medoids clusterin g is solvable in polynomial time for a 2d Pareto front. In World Congress on Global Optimization , pages 790–799. Springer, 2019

  8. [16]

    Dupin and E

    N. Dupin and E. Talbi. Clustering in a 2-dimensional Par eto Front: p-median and p- center are solvable in polynomial time. arXiv preprint arXiv:1806.02098 , 2018

  9. [17]

    Ehrgott and X

    M. Ehrgott and X. Gandibleux. Multiobjective combinat orial optimization - theory, methodology, and applications. In Multiple criteria optimization: State of the art anno- tated bibliographic surveys , pages 369–444. Springer, 2003

  10. [18]

    Elloumi, M

    S. Elloumi, M. Labb´ e, and Y. Pochet. A new formulation a nd resolution method for the p-center problem. INFORMS Journal on Computing , 16(1):84–94, 2004

  11. [19]

    Elshaikh, S

    A. Elshaikh, S. Salhi, and G. Nagy. The continuous p-cen tre problem: An investiga- tion into variable neighbourhood search with memory. European Journal of Operational Research, 241(3):606–621, 2015

  12. [20]

    Eppstein

    D. Eppstein. Faster construction of planar two-center s. In SODA, volume 97, pages 131–138, 1997

  13. [21]

    Ferone, P

    D. Ferone, P. Festa, A. Napoletano, and M. Resende. A new local search for the p-center problem based on the critical vertex concept. In Internat. Conference on Learning and Intelligent Optimization , pages 79–92. Springer, 2017

  14. [22]

    Gonzalez

    T. Gonzalez. Clustering to minimize the maximum interc luster distance. Theoretical Computer Science , 38:293 – 306, 1985

  15. [23]

    Grønlund et al

    A. Grønlund et al. Fast exact k-means, k-medians and Bre gman divergence clustering in 1d. arXiv preprint arXiv:1701.07204 , 2017

  16. [24]

    Guo-Hui and G

    L. Guo-Hui and G. Xue. K-center and k-median problems in graded distances. Theoretical computer science, 207(1):181–192, 1998

  17. [25]

    Hochbaum

    D.S. Hochbaum. When are NP-hard location problems easy ? Annals of Operations Research, 1(3):201–214, 1984

  18. [26]

    Hochbaum and D.B

    D.S. Hochbaum and D.B. Shmoys. A best possible heuristi c for the k-center problem. Mathematics of operations research , 10(2):180–184, 1985

  19. [27]

    Hsu and G

    W. Hsu and G. Nemhauser. Easy and hard bottleneck locati on problems. Discrete Applied Mathematics , 1(3):209–215, 1979

  20. [28]

    Hwang, R

    R. Hwang, R. Lee, and R. Chang. The slab dividing approac h to solve the Euclidean P-Center problem. Algorithmica, 9(1):1–22, 1993

  21. [29]

    Karmakar, S

    A. Karmakar, S. Das, S. Nandy, and B. Bhattacharya. Some variations on constrained minimum enclosing circle problem. Journal of Combinatorial Optimization , 25(2):176– 190, 2013

  22. [30]

    T. Kuhn, C. Fonseca, L. Paquete, S. Ruzika, M. Duarte, an d J. Figueira. Hypervol- ume subset selection in two dimensions: Formulations and al gorithms. Evolutionary Computation, 24(3):411–425, 2016

  23. [31]

    Mahajan, P

    M. Mahajan, P. Nimbhorkar, and K. Varadarajan. The plan ar k-means problem is NP- hard. Theoretical Computer Science , 442:13–21, 2012

  24. [32]

    N. Megiddo. Linear-time algorithms for linear program ming in R3 and related problems. SIAM journal on computing , 12(4):759–776, 1983

  25. [33]

    Megiddo and K

    N. Megiddo and K. Supowit. On the complexity of some comm on geometric location problems. SIAM journal on computing , 13(1):182–196, 1984

  26. [34]

    Megiddo and A

    N. Megiddo and A. Tamir. New results on the complexity of p-centre problems. SIAM Journal on Computing , 12(4):751–758, 1983

  27. [35]

    Mladenovi´ c, M

    N. Mladenovi´ c, M. Labb´ e, and P. Hansen. Solving the p-center problem with tabu search and variable neighborhood search. Networks, 42(1):48–64, 2003. 17

  28. [36]

    Peugeot, N

    T. Peugeot, N. Dupin, M-J Sembely, and C. Dubecq. MBSE, P LM, MIP and Robust Optimization for System of Systems Management, Applicatio n to SCCOA French Air Defense Program. In Complex Systems Design&Management , pages 29–40. Springer, 2017

  29. [37]

    Pulido and C

    G. Pulido and C. Coello. Using clustering techniques to improve the performance of a multi-objective particle swarm optimizer. In Genetic and Evolutionary Computation Conference, pages 225–237. Springer, 2004

  30. [38]

    Ramirez-Atencia, S

    C. Ramirez-Atencia, S. Mostaghim, and D. Camacho. A kne e point based evolutionary multi-objective optimization for mission planning proble ms. In Proceedings of the Genetic and Evolutionary Computation Conference , pages 1216–1223. ACM, 2017

  31. [39]

    Kubushishi

    J-P Rasson and T. Kubushishi. The gap test: an optimal me thod for determining the number of natural classes in cluster analysis. In New approaches in classification and data analysis , pages 186–193. Springer, 1994

  32. [40]

    Samorani, Y

    M. Samorani, Y. W ang, Z. Lv, and F. Glover. Clustering-d riven evolutionary algorithms: an application of path relinking to the quadratic unconstra ined binary optimization prob- lem. Journal of Heuristics , pages 1–14, 2018

  33. [41]

    S. Sayın. Measuring the quality of discrete representa tions of efficient sets in multiple objective mathematical programming. Mathematical Programming, 87(3):543–560, 2000

  34. [42]

    M. Sharir. A near-linear algorithm for the planar 2-cen ter problem. Discrete & Compu- tational Geometry , 18(2):125–134, 1997

  35. [43]

    Sintorn and U

    E. Sintorn and U. Assarsson. Fast parallel GPU-sorting using a hybrid algorithm. Journal of Parallel and Distributed Computing , 68(10):1381–1388, 2008

  36. [44]

    E. Talbi. Metaheuristics: from design to implementation , volume 74. Wiley, 2009

  37. [45]

    W ang and M

    H. W ang and M. Song. Ckmeans. 1d. dp: optimal k-means clu stering in one dimension by dynamic programming. The R journal , 3(2):29, 2011

  38. [46]

    Zio and R

    E. Zio and R. Bazzo. A clustering procedure for reducing the number of representative solutions in the pareto front of multiobjective optimizati on problems. European Journal of Operational Research, 210(3):624–634, 2011. 18 Appendix A: Proof of the intermediate lemmas This se...

  39. [47]

    □ Lemma 10

    Having for a given k, i′ k ⩽ ik, ik−1 ⩽ i′ k−1 is implied by lemma 2 and d(zik , z ik−1−1) > OP T . □ Lemma 10. Let P ⊂ E such that card (P ) /greaterorequalslant2. Let i (resp j) the minimal 20 (resp maximal) index of points of P . We have the following results: ∀x∈ R2− { xi ...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.