# An Objective for Hierarchical Clustering in Euclidean Space and its Connection to Bisecting K-means

arXiv: https://arxiv.org/abs/2008.13235 · HTML: https://mlsanity.com/paper/2008.13235/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2020.

## Built on by (most cited first, 6 of 6)

- [Adaptive Resonance Theory-based Topological Clustering with a Divisive Hierarchical Structure Capable of Continual Learning](https://mlsanity.com/paper/2201.10713/) (2022)
- [On the cohesion and separability of average-link for hierarchical agglomerative clustering](https://mlsanity.com/paper/2411.05097/) (2024)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)
- [LogiPart: Local Large Language Models for Data Exploration at Scale with Logical Partitioning](https://mlsanity.com/paper/2509.22211/) (2025)
- [Rethinking Divisive Hierarchical Clustering from a Distributional Perspective](https://mlsanity.com/paper/2601.19718/) (2026)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)

## Abstract (arXiv)

This paper explores hierarchical clustering in the case where pairs of points have dissimilarity scores (e.g. distances) as a part of the input. The recently introduced objective for points with dissimilarity scores results in every tree being a 1/2 approximation if the distances form a metric. This shows the objective does not make a significant distinction between a good and poor hierarchical clustering in metric spaces. Motivated by this, the paper develops a new global objective for hierarchical clustering in Euclidean space. The objective captures the criterion that has motivated the use of divisive clustering algorithms: that when a split happens, points in the same cluster should be more similar than points in different clusters. Moreover, this objective gives reasonable results on ground-truth inputs for hierarchical clustering. The paper builds a theoretical connection between this objective and the bisecting k-means algorithm. This paper proves that the optimal 2-means solution results in a constant approximation for the objective. This is the first paper to show the bisecting k-means algorithm optimizes a natural global objective over the entire tree.