A sqrt(17/2) Lower Bound for Depth Reduction in Explainable Planar k-Center Clustering

YURAN XIU

A sqrt(17/2) Lower Bound for Depth Reduction in Explainable Planar k-Center Clustering

Primarily AI-generated textHuman understanding: no partscs.CG — Computational Geometry

Contributed by YURAN XIU ↗

Version 1 / Oct 18, 2026 / CC BY 4.0

Abstract

We prove that the factor-

2

lower bound for depth reduction in explainable planar

k

-center clustering is not tight. For every integer

k\ge2

, an explicit set of

4k

distinct integer points has both ordinary and explainable

k

-center radius one, while every axis-parallel threshold tree with at most

k

nonempty leaves and depth less than

k-1

has radius at least

\sqrt{17/2}

. Thus, for every fixed depth multiplier

H

and every

C<\sqrt{17/2}

, arbitrarily large instances admit no such tree of depth at most

H\lceil\log_2(k+1)\rceil

and radius at most

C

times the optimal explainable radius. The point set is a rescaled tail of the ladder of Deng, Gavva, Karthik, Patel, and Srinivasan. The strengthened analysis uses a four-color packing bound and the exact cluster budget to prove rigidity of every sufficiently small-diameter partition, without an explainability assumption. The complete infinite-family theorem and its unbounded-size corollary have been checked in Lean. The existence of a larger universal constant for logarithmic-depth explanations remains unresolved. HAL deposit: hal-05800242v1.

References

Sanjoy Dasgupta, Nave Frost, Michal Moshkovitz, and Cyrus Rashtchian. Explainable $k$ -means and $k$ -medians clustering. In Proceedings of the 37th International Conference on Machine Learning , Proceedings of Machine Learning Research 119, pages 7055--7065, 2020. https://proceedings.mlr.press/v119/moshkovitz20a.html.link
Eduardo S. Laber and Lucas Murtinho. On the price of explainability for some clustering problems. In Proceedings of the 38th International Conference on Machine Learning , Proceedings of Machine Learning Research 139, pages 5915--5925, 2021. https://proceedings.mlr.press/v139/laber21a.html.link
Eduardo Laber, Lucas Murtinho, and Felipe Oliveira. Shallow decision trees for explainable $k$ -means clustering. arXiv:2112.14718v2, 26 August 2022. https://arxiv.org/abs/2112.14718v2.arXiv
Chengyuan Deng, Surya Teja Gavva, Karthik C. S., Parth Patel, and Adarsh Srinivasan. Impossibility of depth reduction in explainable clustering. arXiv:2305.02850v2, 2 March 2026. https://arxiv.org/abs/2305.02850v2. The cited construction, theorem, and open problem are Section 4.1, Theorem 4.1, and Open Problem 1 of this version.arXiv
WADS 2023. Open Problems from WADS 2023 , 3 August 2023. Open Problem 6, ``Depth-Reduction for Explainable $k$ -Center,'' posed by Chengyuan Deng, page 3. https://wadscccg2023.encs.concordia.ca/assets/pdf/wads_open_problems.pdf.link

Version history

v1Submitted by YURAN XIUInitial depositCurrentOct 18, 2026