A  Single-Swap Local Search Algorithm for k-Means of Lines
Authors: Ting Liang
Xiaoliang Wu
Junyu Huang
Jianxin Wang
Qilong Feng
Venue: NeurIPS 2025 poster ()
Keywords: local search，line clustering，k-means of lines
Primary area: general_machine_learning

Abstract: Clustering is a fundamental problem that has been extensively studied over past few decades, with most research focusing on point-based clustering such as $k$-means, $k$-median, and $k$-center.
However, numerous real-world applications, such as motion analysis, computer vision, and missing data analysis, require clustering over structured data, including lines, time series and affine subspaces (flats), where traditional point-based clustering algorithms often fall short.
In this paper, we study the $k$-means of lines problem, where the input is a set $L$ of lines in $\mathbb{R}^d$, and the goal is to find $k$ centers $C$ in $\mathbb{R}^d$ such that the sum of squared distances from each line in $L$ to its nearest center in $C$ is minimized. The local search algorithm is a well-established strategy for point-based $k$-means clustering, known for its efficiency and provable approximation guarantees. However, extending local search algorithm  to the $k$-means of lines problem is nontrivial, as the capture relation used in point-based clustering does not generalize to the line setting. This is because that the point-to-line distance function lack the triangle inequality property that supports geometric analysis in point-based clustering. Moreover, since lines extend infinitely in space, it is  difficult to identify effective swap points that can significantly reduce the clustering cost. To overcome above obstacles, we introduce a *proportional capture relation* that links optimal and current centers based the assignment proportions of lines, enabling a refined analysis that bypasses the triangle inequality barrier. We also introduce a *CrossLine* structure, which provides a principled discretization of the geometric space around line pairs, and ensures coverage of high-quality swap points essential for local search, thereby enabling effective execution of the local search process. Consequently, based on the proposed components, we develop the first single-swap local search algorithm for the $k$-means of lines problem, achieving a $(500+\varepsilon)$-approximation in polynomial time for low-dimensional Euclidean space.

A Single-Swap Local Search Algorithm for k-mmaans of Lines
Ting Liang', Xiaoliang Wu', ,unyu Huang' Jianxin Wang" Qilong Feng!
School of Computer Science and Engineering, Central South University
The Hunan Provincial Key Lab Bioinformatics, Central South University, Changsha 410083, China
tingliang@csu. edu. xiaoliangrucau@116 ctt.suuuee......... com, junyhuunneceufoommllllccc zwang@mail. csu. edu. cn, caufeng@maill cau. edu.
Abstract
Clustering is fundamental problem that has been extensively studied over past few decades, with most research focusing on point-based clustering such as k- means, k-median, and k-center. However, numerous real-world applications, such as motion analysis, computer vision, and missing data analysis, require clustering structured data, including lines, time series and affine subspaces (flats), where traditional point-based clustering algorithms often fall short. In this paper, we study the k-means of lines problem, where the input is and the goal is to find centers C' in Rd such that the sum of squared distances from each line in L to its nearest center in C' minimized. The local search algorithm is well-established strategy for point-based k-means clustering, known for its efficiency and provable approximation guarantees. However, extending local search algorithm to the k-means of lines problem is nontrivial, as the capture relation used in point-based clustering does not generalize to the line setting. This is because that the point-to-line distance function lack the triangle inequality property that supports geometrie analysis point- basee clustering. Moreover, since lines extend infinitely in space, it is difficult to identify effective swap points that can significantly reduce the clustering cost. To overcome above obstacles, we introduce proportional cupture relation that links optimal and current centers based the assignment proportions of lines, enabling a refined analysis that bypasses the triangle inequality barrier. We also introduce CrossLine structure, which provides a principled discretization of the geometric space around line pairs, and ensures coverage of high-quality swap points essential for local scarch, thereby enabling effective execution of the local search process. Consequently, based on the develop the first single-swap local search algorithm for the k- k-means of lines problem, achieving (500 + approoxiiatiionn in polynomial time for low-dimensional Euclidean space.
L of lines in R&
proposed components,
Introduction
Clustering is one of the most popular problems machine learning, and has lots of applications in data mining, image classification, etc. The goal of clustering is to partition given set of points into several disjoint clusters such that similar points end up in the same cluster, and dissimilar points are separated into different clusters [23]. Among classical clustering models [11, 12, 25]. k-means is one of the most extensively studied, aiming to minimize the total squared distance from each data point to
Corresponding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

its nearest center. More formally, given set P R of n data points in a d-dimensional Euclidean space and a positive integer k. the goal of k-means is find a set C' R of centers such that the objective Eper min.ec ||c- - pll is minimized.
Although the k-mmans problem is NP-hard [21, 15], numerous approximation algorithms have been developed. One of the most widely used heuristics in practice is Lloyd's 'ss algorithm [17], even though it lacks provable worst-case approximation guarantees under general data distributions. To establish approximation guarantees, researchers introduced a series of algorithms based on primal-dual and randomized rounding techniques (2. 10], among which a primal-dual method leveraging nested muasi-independen sets [5] achieves the best-known approximation ratio of 5.912. Meanwhile, local search has emerged as a practical and theoretically grounded framework for the k-means problem. Several local search algorithms [6, 7] achieved a (1 + >)approximationn under the assumption of fixed dimension d or a constant number of clusters k. To further enhance the initialization, Arthur and Vassilvitskii [3] proposed an efficient seeding algorithm, known as k-means++, which achieves an (log k -approximatiin in expectation. Subsequent studies [26, 1, 19] showed that k-means++ achieves constant-factor approximations when allowed to open O(k) centers. Building upon this, Lattanzi and Sohler [16] proposed the LS++ algorithm by combining k-means++ seeding with local search, achieving a constant- factor approximation in Onddk2 log log k) time. Choo el al. [4] further improved its efficiency, demonstrating that an 0(1 (e)) >apprrximmatiioo can be obtained using only (EEk) local search iterations. Under the assumption that each optimal cluster has size ((n/k). Huang al. [13] proposed a fast and practical local search algorithm for k-means problem, and achieved a (100 + =) approximation in expectation. More recently, Huang et al. [14] gave the first multi-swap local search algorithm with running time linearly dependent on the data size, and achieved a (50 (1 + ?) + e) >appproximation with any swap size t 2 2 in time O (nddk2 log (s- log k)). improving the previous 509 approximation under linear-time constraints.
While these results provide strong theoretical and practical foundations for point-based clustering, many real-world applications involve structured data that are more naturally represented as geometric objects such as one-dimensional affine subspaces (i.e., lines). For example, in computer vision [18, 20]. when multiple cameras are used to observe set of fixed objects, each camera provides directional observation, that is, a direction vector from the camera to the object. By combining each camera with its corresponding direction, set of lines can be obtained. Clustering these lines helps identify different objects and recover their locations, since the lines corresponding to the same object tend to intersect or near the object's 'ss true location. This motivates the study of clustering problems where the input consists of lines rather than points. Although conceptually similar to classical point-based formulations, line clustering introduces unique algorithmic and geometric challenges, and remains relatively underexplored in the literature. Among the few existing studies, Har-Peled and Varadarajan [8] studied the problem of finding the minimum intersection radius of a set of lines or affine subspaces, and introduced a substitute for the triangle inequality based on novel analog of Helly's theorem. Aronov et al. [9] studied the problem of finding k minimum- radius balls in Euclidean space that intersect all given lines, and developed 2-approximation algorithm for k= 2,3 3 with quasi-linear running time. Ommer et al. [22] considered the k-means of lines problem, and proposed the first heuristic algorithm without theoretical guarantee and time constraints. Perets er al. [24] proposed an approximation algorithm in R²² that starts with bi-criteria approximate solution, and then uses the coresets technique, achieving (1 + E) a)approxximation in time OO (l)) ((()) for any given parameter E > O. Further, Marom et al. [20] developed an algorithm for the k- k-means of lines problem that computes an e-coreset of size O(d log(n)/e²) in time Oddnn n log(n)k ) log k + (d/=)² + (d)))
In this paper, we focus on the k-mmaas of lines problem. Given a set L of n lines in Rd and an integer & E N21,, the objective is to find set of k centers C' C Rd that minimizes the total squared distance from each line E L to its nearest center in C. In this paper, we present the first local search algorithm with provable approximation guarantees for the line-based setting. Although local search has been extensively analyzed for point-based k-means due to its simplicity and strong empirical performance, extending it to the line setting introduces several fundamental challenges. To motivate our algorithm, we first review the classical local search framework and highlight the key obstacles in adapting it to line clustering.
The standard analysis of local search algorithm for k-means mainly relies on a capture relation, in which each optimal center is captured by the nearest center in the current
2

---

solution, such that it is easy to analyze the change in clustering cost incurred when points are reassigned in the process of local search. However, the above relation not workable for the line setting, since the assignments of lines may be determined by an optimal center that not the closest in Fuclidean distance, and reassigning lines hased solely on geometric closeness can lead to significant increase in clustering cost.
The sampling-basee method a commonly used technique in local search. However, unlike the point setting, it is more challenging to sample a point close to the optimal center from these lines, since the optimal center is unknown and each line spans a continuous space of candidate points, even show that the cost of high-cost cluster can be effectively approximated by lines that are close to their optimal center in the h-means of lines problem.
Our Contributions. To overcome these obstacles, we introduce new proportional capture relation and a structured sampling technique tailored to the geometry of lines. Specifically, we define that an optimal center is captured by current center if it receives the largest fraction of lines from that center, enabling a more faithful representation of line-to-center influence. To facilitate effective sampling, we further design a discretization structure, called CrossLine, which guarantees the existence of point near the optimal center within a bounded region defined by two sampled lines. This structure allows us recover, with provable guarantees, good replacement center from a finite set of representative points. We formalize the proposed proportional capture relation and CrossLine structure in Section 3, and discuss some key properties. Building on these foundations, we develop the first local search algorithm for the k-means of lines problem with provable approximation guarantees. The main contributions of this paper are summarized follows:
In two-dimensional space, we introduce a proportional capture relation and a geometry- aware discretization structure CrossLine, both tailored to the challenges of line-based clustering. These tools enable an accurate representation of line-to-center assignments, and support efficient sampling from continuous line domains.
In high-ddmensional space, the existence of skew lines makes the CrossLine structure in R² inadequate. To address this issue, we redefine the CrossLine structure to accommodate high- dimensional geometry, ensuring that the coverage guarantees remain valid under arbitrary line orientations.
Building upon these tools, we propose the first single-swap local search algorithm for the k-means of lines problem, achieving a (500 + apaarooxxintionn and running in polynomial time on low-dimensional Euclidean space.
Extensive experiments on both synthetic and real-world datasets show that our algorithm consistently outperforms pereset-based baselines in both efficiency and clustering quality.
Formally, we have the following results this paper.
Theorem 1. For any > O, there exists a local search algorithm for the k-means of lines problem, which achieves (500 + apprroximaaio in expectation with polynomial time on low-dimensional Euclidean space.
2
Preliminaries
For any positive integer m E N21, let [m] = (1....,m). m). Given a set P S Rd of points, for any p.q P. let 8(p, q) = ||p 41i denote the square Buclidean distance between p and q. Given any two set A, B C Rd of points, for any p E A, let 5pp B) minge 5(p 9) denote the shortest square distance from p to any point in B. Further, let 8(A, B) = milgeA..e 6(p, q) denote the square distance between A and B, and let () Epea 8(p, B) denote the sum of distances from each point in A to its nearest point in B. Given nonempty subset C C P of centers, for any e C' and a radius r, ball B(c,r) is the set of points that are within a distance r from c, i.e., B(c,r) = (p E P 8(c,p) p) Sr). Given a set of lines in Rd and a set C C Rd of points, for any E L, let o(e, C) = min.eo c). where ò(t, c) is the shortest square distance from any point on the line to c. Formally, the k-means of lines (denoted as k-MI.) problem considered in this paper can be defined as follows.
3

---

Algorithm 1: SLS-k-ML
Input: An instance (L, d, k) of the k-ML problem and parameter T Output: A C C Rd of at most l centers
P + CENTROID-SET(L)
C' Sample k points from P randomly;
3 for i E f1,2...., do Sample two lines 6, f2 from L with probability be MeE Alle),o) (l {11, (l, E2))
A((()
.M <- the point set returned by Crossline of (f1,62); f2);
for each point p E M do if C. s.t. ALL, Cxta U (p)) < ALL, C) then
C Cita
return C.
Algorithm 2: CENTROID-SET
Input: A finite set L of n lines in Idd
Output:
of points
P + 0;
2 for each line L do
Pz + 0;
for each line E' E [V( do Te (L) the closest point on / to 8';
P Pe (f)}
P PUPE
return P.
Definition 1 (the k-ML problem). Given set L C Rdd of n lines in d-dimensional Euclidean space and a positive integer k the goal is to find set C C RRd of k centers such that the objective ALL,C) Eiel 8(E, C) is minimized.
In this paper, we assume that all lines in L are pairwise non-parallel (possibly intersecting or skew), ensuring distinct directional relationships and avoiding degenerate configurations. Given instance (L, d, k) of the k-ML problem, C' is called a feasible solution of this instance if C' C IRd is set of k points. Throughout this paper, let C* {ct ..., d be the optimal solution and {L(ct). (oct)...... L(c))) be the corresponding optimal clusters by assigning each line in L to its closest centers in C Let
(I, C**) be the cost of the optimal solution C*"
Local Search Algorithm with Single-Swap Strategy
The local search algorithm for the k-means problem typically begins with a candidate set of centers and iteratively replace one more centers, as in single-swap multi-swap strategies, to progressively reduce the clustering cost. Unlike classical k-means problem, which benefits from effective initial- ization algorithms such as k-means++ [16], the k-ML problem lacks a well-established algorithm for constructing a high-quality initial solution. Therefore, necessary to explicitly construct an initial solution for the k-ML problem. Moreover, extending local search algorithm to the k-ML problem introduces additional challenges beyond initialization. Specifically, the capture relation used in k-means problem does not hold in the line setting, as line assignments are governed by projection distances, and reassigning a line to the optimal center closest to its current center may lead to an increase in clustering cost. In addition, it is more challenging sample point that is close to optimal center from given lines, since the optimal center is unknown and each line spans a continuous space of candidate points.
To overcome these challenges, we develop a single-swap local search algorithm for the k-MI. problem, referred to SLS-k-ML, which is presented in Algorithm 1. Our algorithm SLS-K-ML consists of

---

two stages. In the first stage (steps 1-2), the algorithm starts with a centroid set P obtained by CENTROID-SET that reduces the lines in L set of points. Then, we obtain a feasible solution C' from the constructed centroid set P with an approximation guarantee. In the second stage (steps 3-8), we execute the single-swap local search with 7 iterations. In each iteration, the algorithm first to sample two lines 21, l2 from L with a probability, and then constructs candidate swap pairs based on the CrossLine structure with respect to & l2 to find improvements. The CrossLine structure ensures that each optimal center can be effectively approximated by at least one grid point. Under the proposed proportional capture relation, such a grid point can be used to replace a current center, resulting in reduction of the clustering cost.
3.1 Construct an Initial Solution
This section shows how to construct an initial solution with an approximation guarantee for a given instance of the k-ML problem in polynomial time. It is known that the local search algorithm typically begins with an initial solution. However, the k-ML problem lacks a well-established algorithm for generating high-quality initial solution. Therefore, we first need to construct such an initial solution as a foundation for the local search process. To this end, we first construct a candidate point set P by the CENTROID- each line, CENTROID-SS SET computes its the closest points to all other lines, and collects them into a candidate set P of (n²² points. We then obtain the initial solution C' by sampling k points uniformly at random from P. In the following. we show that the initial solution C' provides a constant- factor approximation to the optimal clustering cost, and can be computed in polynomial time.
procedure from [20] (see Algorithm 2). Given set L of n. lines in R for
Lemma 2. Given an instance I = (L, d, k) of the k-ML problem, let C be the set of points returned by step 2 of SL.---MI... Then, for a finite constant p. we have (TT, C) $ p C"),C")) (see Appendix A. I for proof).
3.2 Single-Swap Local Search R²
To facilitate understanding of our proposed algorithm, this section focuses on the single-swap local search process in IR? Specifically, we construct a swap pair between the center in and a candidate center in M obtained by the CrossLine structure, which is related to two lines sampled from L with a specified probability. If the clustering cost reduced, we update the current solution by replacing the center in C' with the candidate center from M. In the following, we show that if the current solution has a high cost (greater than 500r), then the clustering cost can be reduced with a certain probability in each iteration.
Lemma 3. Let C C R22 be a set of centers with (T,, C) > 500r, and let C' be the set of centers obtained in the t-th (t (T) iteration of SLS-k-MI.. in step 8. Then, with probability at least S2(--1),
we have (LI, C²) S (1 100k ALL C), where ( is a constant.
Before proving Lemma 3, we first analyze a single-swap (w.Lo.g. t-th iteration) in steps 3-8 of SLL---ML. Let C = (ci.....Co ... denote the set of centers before the t-th swap operation, and let (L(c). L(cx)} be the corresponding partition of L induced by assigning the lines to the closest center in C. For clarity, when the specific index is not relevant, we omit it and simply write, for example, c C. Motivated by the local search for k-means [16], we adopt similar strategy to analyze the cost reduction by comparing the current and optimal center sets. Specifically, the algorithm in [16] introduces the notion of capture relation, which states that an optimal center can be captured by the nearest center in the current solution. However, the above relation relies on a point-to- point assignment setting, and is not workable for our problem, since the data consist of lines and the clustering cost is based on projection distances. For example, in the k-means setting, for each e C* assume that i the closest center in C' to c*. By the capture relation, the optimal center c* is captured by c, which means that e is the nearest center to c* among all centers in C. In the process of analyzing local search, we consider replacing with a point near c*, and reassigning the points in the cluster of thereby achieving a reduction in clustering cost. However, in the line setting, the lines in the cluster of e may be significantly closer to another optimal center in C" In such case, we reassign these lines to a point near to c", the clustering cost will drastically increase, indicating that the original capture relation does not generalize to the k- ML problem. Therefore, we propose a proportional capture relation better suited to the line setting: an optimal center e E C" is captured by center e E C' if e assigned the largest proportion of lines from the cluster of e among all center in C. Clearly, center e C' may capture more than one optimal centers, and every optimal
5

---

center is captured by exactly one center from C. For a center c E C, let (c)) be the set of centers in C* captured by c. For each optimal center E C", let (c*) be the center in C capturing e². Further, we introduce two types of matched swap pairs that correspond to the two cases encountered in local search as follows.
The type-1 matched swap pair: For any C C, [N) = 1 (i.e., ((c) contains only one optimal
center c²), we define (c) as a type-1 matched swap pair. Let Css denote all centers in C' satisfying the property of type-1 matched swap pair. For simplicity, we introduce a mapping Vs : Cs + C* that maps each center in Cs to an optimal center in C* such that (c. (c)))) a type-1 matched swap pair. For each type-1 matched swap pair (c, sc)) (c E Cs). we replace the current center e with a point near the optimal center (c). For a type-I I matched swap pair, the lines in cluster (c Cs) can be divided into two groups: The first group consists of lines that belong to both the current cluster of e and the optimal cluster of (c).). These lines are reassigned to a point near their optimal center, leading to reduction in clustering cost. The second group consists of lines that belong to in the current cluster of but not to the optimal cluster of (c). These lines are reassigned to other centers in C, which may increase the clustering cost.
The type-2 matched swap pair: For any E C, (c]) = 0 (i.e., c does not capture any optimal center), we can find another center c' E C' with [W(c)] > 1, and assign one of its captured optimal center E [ccc') to form a type-2 matched pair (c.c*). Let Cy denote all centers in C satisfying the property of 2 matched swap pair. For simplicity, we introduce a mapping uhy CN - C* type-2 matched
that maps each center in CN an optimal center in C* such that (c, (c)) swap pair. For a type-2 matched swap pair (c, (c)) (c E CN). we replace the lonely center with a point near the optimal center v (c). Similar to the type-1 case, the lines in cluster (e E Cx)) also can be divided into two groups: The first group consists of lines that belong to the optimal cluster of (c). These lines are reassigned to a point near their optimal center, leading to a reduction in clustering cost. The second group consists of lines that belong to the current cluster of c. These lines are reassigned to other centers in C, which may increase the clustering cost.
Through this construction, each optimal center in C* is paired with a current center in C' via exactly one type-1 or 2 matched swap pair. Each swap pair involves both clustering cost reduction (from lines reassigned to sampled point near their optimal center) and clustering cost increase (from lines reassigned to potentially farther centers). the following, we will argue that with high probability, a point can be sampled to perform the swap operation such that the resulting reduction in clustering cost significantly bigger than the corresponding increase. For a type- or type-2 matched swap pair, we refer to the clustering cost increase as the reassignment cost, which is formally defined below.
Definition 2. For any c E Cs, the reassignment cost of the type-1 I matched swap pair (c, (c)( - A(IAI(c'), C), where c = (bs(c). Similarly, for any e E ON. the reassignment cost of the rype-2 matched swap pair (c. th (c)) is defined as na(c)= A(L, C'((t)) - A),
is defined (c) A(I)L(("),
Lemma 4. For any E Cs (or e E CN), the reassignment cost ni (c)c) (or n2(c)) is at most T AAL(O), C) 24A()(c)) C*) (see Appendix A.2 for proof).
Lemma 4 implies that there exists a good bound on the reassignment cost. To proceed, we discuss the following two cases based on the cost contributions of type-1 and type-2 matched pairs: Case I: Erecs ALL(v((c)), C) > A(L, C). Case 2: Enecs A(L(vs(c)), C) < 3 A(L, C), thus
E Eeec" (c) A(L(c), C) N Cale
A(L,C).
3.2.1 The Analysis of Case
Recall that the definition of type-1 matched swap pair (c, (s(()) (c E Cs), we replace the current center e with point near the optimal center (e),), with the goal of achieving a significant reduction in clustering cost. We refer to such clusters that yield a significant cost reduction as good clusters, and we formalize this notion below.
Definition (Good type-1 cluster). For any e E Cs, the cluster L(c) is called a good type-1 cluster, if A(L((s(()) C) - (c(c) (A(L()s(c)), (vs(c))) > 1ook A(L, C). Otherwise, L(c) is called a bad type-l cluster with (c, (c))
For simplicity, let C2 denote the set of centers in Cs for which the corresponding cluster is good type-1 cluster. Let C. Cs..O. The Definition 3 estimates the cost reduction of replacing with

---

point close to (c) by considering a cluster that reassigns the lines in L(e) ((e)))L((bs((e ((bs(c)). and assigns all lines in L( (c)( the new center. We now aim to show that a good type-1 cluster can be sampled with high probability. To this end, we first argue that the total clustering cost contributed by good type-1 clusters is sufficiently large. Then, we show that with good probability, we can sample a point that is close to the center.
Lemma 5. 3 EcEcs AlL(Vs(e)), C) > A), then we have Eeecanog AlL(vs(c)), C) 1 50
ALL, (see Appendix A.3 for proof).
Then, we show that with good probability, point close to the optimal center of good type-1 cluster is sampled. To prove this, we first establish the following the technical lemma.
Lemma 6.
Let be a set of lines in Rd, and let e, E Rd be two points. Then, the total squared distance from the lines in L
satisfies: ALL (ct) I 3|L| d(c,e') + 6 ALL where ALL [c})= Eier ö(l, c) and ô(L, c) denote the squared Euclidean distance from line to point c, respectively (see Appendix A.4 for the proof).
This lemma, used in the proof of Lemma 6, shows that the clustering cost of any two centers is related to the distance between the centers. In the following lemma, we show that if a cluster with respect to C' incurs a large clustering cost, then the subset of lines located near its center likewise contributes a comparably high cost.
Lemma 7.
Let Q be set of lines in Rd, let C' S Rd be set of k centers, and let ct be the optimal single center for Q. Assume a 2 9. If the cost under C satisfies AQQ, C) 2 a (QQ, {c' )) then A(Q,cc)). where R = {e E Q 8((,c)) S
there exists a subset R S Q with ARR, C) 2
a-1 24
2 AQ, {ct})} (see appendix A.5 for proof). Q
To find a point near the optimal center along a line, we first evaluate the probability of sampling a line close to the optimal center. For any e E Cs. we have (LL(vs(c)), C* > 9 ALL(vs (c)), (vs(c))) due to Definition 3. Then, by applying Lemma 7 with Q = [(bb(()) and a = 9, we get that (AA, C) 2
a-1 A(L((s(e)), {c)(c))) 24n (LL(vs(e)), C) 2 27 (C)(vs(c)). C), where
a-1
24
A is the set of lines within distance (eddeeel)))ssse from vs(c).. By Lemma 5, we can obtain that EeeCencg C(L( N 50 ALL, C). Thus, we conclude that the total cost over all 27-30 ALL, implying that the However, since A is set of lines rather than points, we cannot directly select line as a candidate center. Instead, we need to generate a set of points from the lines in A, and ensure that at least one of them lies within distance 24(Livg(c)), (vs(()) from the optimal center. To proceed, we introduce geometric discretization (c))]
sets A from good clusters satisfies ExEcenog ((A,C) 2 probability of sampling line from Usecencg A is at least 1500
structure, referred to as y-CrossLine, and prove that the set of points returned by this structure contains at least one point that lies within distance r of any point inside the structure.
Definition 4 (r- CrossLiLeee in R2?. Let E and Ez be two intersecting lines in R?, intersecting at a point p & E2. For each line Eg (i = 2). construct two lines parallel l, by shifting it along its normal direction by tr. Let L1 = parallel lines derived from &a and f2, respectively. The i-CrossLinee is defined as the union of all regions enclosed by the lines in Li and Lz, and Crossl.ne,, L2) = (4 | Ei, Eg E L2] denotes the set of all pairwise intersection points.
and Eg = {(z l2, Er denote the sets of three
Based on Definition 4, we prove that for any point inside the r r-CrossLine, there exists at least one grid point within distance r it.
Lemma 8. Let E and & be two intersecting lines in TR2 and let r > 0 be a constant. Then, for any point x within r i-CrossLine, there exists at least one grid point from CrossLine, (E1, E2) whose distance to x is at most r. (see Appendix A.6 for proof).
As mentioned earlier, A is the set of lines within distance 24(L(vs(e)) (ws(())) from (c(()). and the [Z(''s (c)) probability of sampling line from the set UceCsncg A least 1500 Therefore, the probability that both & and &g lie in A is at least Ç = ((1t)) Assuming that & lg E UceCance A, =
2A(L. (v)s() let CrossLine, (l1, E2) be the point set obtained by Definition 4 based on E [[))
7

---

and 62. Then, by Lemma 8, CrossLine, (41, E2) contains at least one point within distance r of the optimal center, which can be used as hugh-quality swap candidate. However, since the radius is defined in terms of the (unknown) optimal cost, we adopt a multi-scale, data-driven schedule: let rmin and m'max be empirical scales around the intersection (e.g., lower/upper quantiles of the distances from the intersection to the candidate set returned by Algorithm 2). We progressively explore the search radii ri E ['10", Tmax] constructing an r CrossLinee around the intersection at each scale and performing a single-swap at every step until an improvement is found. By construction, at least one of the radii re lies within a constant factor of the theoretical radius r. At this scale, Lemma guarantees constant probability of success. By Definition 3, if such point p is obtained, can swap it with c to get new clustering with cost at most ALL, C' \ {ca] U {p)) S ALL C)
((L(Ws(C)), C) + (c(c) + (CL(Ws())) fet). By Lemma 6, we have that ((L(W)(C)) {c)) < 9 (L((ss()) (vs(c))) Thus, with a constant probability, the new clustering has cost at most ALL, - (A(L(Us(C)) C) - mi(c) - (css)))()) {bs(c)))) S (1 I A(L, C).
3.2.2 The Analysis of Case 2
For type-2 2 matched swap pair (c, (c() (c E Cx), we similarly define clusters that yield a significant reduction in assignment cost under such swaps as good clusters, as formalized below.
Definition (Good type-2 cluster). For any c E CN, the cluster L(c) is called a good rype-2 cluster, if (LL(éN (c)), C) (e(c)) - (A(L((x(e)), (c)(())) > 100K (L, C). Otherwise, L(c) is called a bad type-2 cluster with (c, (c()))
For simplicity, let C% denote the set of centers in Cy for which the corresponding cluster is good type-2 cluster. Let C% = CN CC* The above definition estimates the cost reduction of replacing e with a point close to (s(c) by considering cluster that reassigns the lines in L(c) and assigns all lines (c)) to the new center. We now aim to show that good type-2 cluster can be sampled
with high probability. To this end, we first argue that the total cost contributed by good type-2 clusters is sufficiently large.
Lemma 9. If Excoroo ([)),(e)), C) 2 EEE A(T(WN(e). 2 30 A(T,, C.) (see Appendix A.7 for proof).
3
A(I,
then we have
Note that in this case we can now argue similarly as in the other case that sampling according to sum of squared distances will provide us with constant probability with good center using
Lemma 7. Indeed, since the sum of squared distances of lines in good centers is at least 1 A(L, C)
50
by Lemma 9, it follows together with Lemma that we sample a point from a good cluster L (c))
that is within distance two times the average cost of the cluster with probability 1500 By the
definition of good cluster, we have that such a point improves the cost of the current clustering by
at least factor of (1 Took
(1=10xx) )- Thus, by combining Case 1 and Case 2, we complete the proof of
Lemma Now we complete the proof of Theorem 1. Let È be the set of centers returned by step 2 of SLS-K-MI. which achieves a p-approximation guarantee by Lemma 2. Let C' be the set of centers returned by St.S-K -MI. By Lemma 3, we know that if the current cost exceeds 500r, then with probability at least ((1/p), single iteration of SLS-K-N. ML reduces the cost by factor of (1 Toor). ). We introduce a random process X to analyze the change of the clustering cost. The process starts at A(T., C), and over T = 100k log steps, it decreases multiplicatively by factor of (1 100R) ) with probability 1/Ç at each step, and finally increases additively by 5007. Furthermore, TdbR ) = A(.., C)(1
E[X]= 500 r + AT. C) Σ (+)
1 1100k logo_
1ook?
5007 < A(L.2 + 500T. This implies that E[A(L, | č7 < ALL, + 5007. Then, we have
P
EJA(L, C)] = Ee C|A(L.C) | Ō1 Pr(O) = Eo Pr(C) ALLO) + 5007) < (500 + E)r.
Running Time Analysis. The overall time complexity of SLS-k-ML is 0(n Clo p). The first stage of constructing the initial solution takes On²)) time, as it involves constructing the candidate set using the CENTROID-SET procedure, which takes O(n²) time, and sampling k points from the candidate set, which takes 0(1) time. To achieve (500 + >)aaprooxima solution, SLS-K- ML requires O(k log p) iterations. In each iteration, sampling two lines takes Ologg)) time, constructing the Crossline structure takes O(1) time, finding swap points from the CrossLine output takes (1) time, and updating the distances between all lines and their nearest centers takes O(nk)
8

---

time. Therefore, the total running time of the iterative procedure is O(nk"ç p), and the overall time complexity of SLS-k-Mi is O(n² + nk² (og p).
3.3 Extended to IR"
In this section, we show how to extend our algorithm to the general case in R In R. the the existence of skew lines makes the CrossLine structure in I² inadequate, as lines may not intersect and can lie on different affine subspaces. To address this, we redefine the CrossLine structure to accommodate high-ding high-dimensional geometry, ensuring coverage guarantees remain valid under arbitrary line orientations. Moreover, in R" the reassignment argument remains valid, while the bound must be adjusted to account for the dimensional dependence in the projection geometry. Formally, we restate the following result for R.d
Lemma 10. For any c E Cs (or e E Cx). the reassignment cost vn (c) (or n2((c) is at most 5 ()(()) + (T)( C*) (see Appendix A.8 for proof).
Note that although Lemma and Lemma 10 yield the same conclusion, they are derived in different contexts and serve distinct purposes within the analysis. The second difference lies in the construction of the CrossLine structure, Recall that in I2, we generate a constant-size candidate set based on the intersection and perturbation of line pairs. In R this structure must be extended to cover a higher- dimensional geometric region induced by two non-parallel lines. Specifically, for each pair of lines, construct discretized grid over the intersection of their respective r-bounded neighborhoods, which forms a d-dimensional crossline region. Note that in the process of constructing the candidate set in Rdd retain the same discretization resolution as in the planar case, but extend it across all d orthogonal directions to ensure sufficient coverage for sampling high-quality swap points. We now introduce the required extensions the candidate set construction.
Definition 6 (r-CrossLine in Rd).. Let l C Rd be two non-parallel lines. For each line l (i 1,2), we define the set 3d axis-aligned parallel shifts as L. = (1 = l +++E Ei+Es=1 S..r.ej 8 {-1,0,1)4) where ej is the unit vector in the j-th coordinate direction. We define the CrrossLiine as the union of all regions enclosed by the lines in Ln and L2, and CrussLine, (2) {en n ll EE ELL, E' E L2, E # 03. Assuming each pair of lines (e, ()) intersects (e.g. due to careful shift alignment in a common plane), the total number of grid points is at most |CrossLine, (l,, S 32d
Based on the r-CrossLine in Rd, we restate Lemma 8 as follows.
Lemma 11. Let ( and l2 be two intersecting lines in R&, and let > 0 be a constant. Then, for any point within r-CrossLine, there exists at least one grid point from CrossLine, (E1, Eg) whose distance to x is at most r (see Appendix A.9 for the proof)-
Running Time Analysis. The overall time complexity of St.S-k-ML is (n + ga (log p). The first stage of constructing the initial solution takes O(n2d)) time, as involves constructing the candidate set using the CENTROID- -ET procedure, which takes Onn²df) time, and sampling k points from the candidate set, which takes O(1) time. To achieve a (500 + -ppapooxiia solution, SLS-k-ML requires Okç log p) iterations. In each iteration, sampling two lines takes Ollog n) time, constructing the CrossLine structure takes O(1) time, finding swap points from the CrossLine output takes O(9e) time, and updating the distances between all lines and their nearest centers takes (Iddk) time. Therefore, the total running time of the iterative procedure is Od9 { log p). and the overall time complexity of SLS-k is ?n? nlnn?? ( Çlog
4 Experiments
In this section, we give empirical evaluations on the performances of our proposed algorithms. All algorithms are implemented and executed in Python. The experiments were done machine with 17-14700KF processor and 256GB RAM.
Datasets. We evaluate the performance of our algorithm on both synthetic datasets (SYN 1 with n = 5000, = 10, and SYN2 with n 10000, d = 5) and real-world OpenStreetMap datasets (RE I with = 476, d = 2, and RE 2 with 418, d = 2) as used in [20]. For each dataset, we run both algorithms 10 times and report the minimum cost (Min_Cost) Cost), maximum cost (ost),, average cost (Arg_ Cost), standard deviation (Std), and runtime (Time(s)).

---

Table I: Experimental results of our SLS-k-ME algorithm and the coreset-based method.
Datasets
Method
k
Cost Max_Con Cost
Aug_ Cost
Std
Time(s)
SLS-k-ML(OUus)
10
8.37E-10
1.72E-06
101E-07
2.73E-07
1.05
RE
Coreset+sampling
10
8.17E-04
3.08E-02
6.24E-03
5.89E-03
6.05
Coresct-exhaustive search
10
Over 12 hours
SLS-k-ML(Ours)
3
5.67E-06
1.15-003
1.35E004
2.00E-04
0.71
RE
Coreset+sampling
1.57E-02
8,78E-01
1.39E-01
1.95E-01
4.08
Coreset+exhaustive search
3
1.10E-03
2.11E-03
1.56E-03
3,01E-04
93.97
(Our))
10
1.35E-08
3.16E-05
1.60E-06
4.66E-06
1.40
RE 2
Coresct+sampling
10
2.89E-03
1.20E-01
2.16F-02
2.13E-02
3.34
Coreset+exhaustive search
10
Over 12 hours
SLSs-k-ML(Ours)
3
1,45E-05
5.59E-03
1.39E-03
1,18E-03
0.43
RE 2
Coresct+sampling
3
4.88E-02
6.11E+00
6.21E-01
1.08E+00
4.91
Coresct-cxhaustive search
3
4.69E-04
4.83E-03
2.51E-03
1.09E-03
2.59E+02
SL.--k-ML(Ours)
10
1.84++04
1,88++04
1866+04
1.97E+02
4.56E+002
SYN
Complig+
10
3.97E+04
4.51E+04
4.24E+04
2.70E+03
2. 2.04E+04
Coreset+exhaustive search
10
Over 12 hours
SL.s-k-M1.(Ours)
3
1.87E+04 1,98++04
1.984+04
5,45E+02
1.15E+003
SYN
Sarpsen+sampling
3
Over 12 hours Over 12 hours
Coreset+exhaustive search
3
Algorithms. In our experiments, we give comparisons between our local search algorithm and the coreset-based method from [20]. For coreset-bases method, we compress the data with their coreset algorithm and select centers via sampling exhaustive search, For our SLS-k-ML. algorithm, we design a sampling strategy that selects a subset of 100 points from r-CrossLine to improve computational efficiency. Following the settings in [14], we set the number of sampling rounds to and 10.
= 400, and the number of clusters to
Results. Table shows that our proposed SLS-k-ML algorithm always achieve the best performance compared with cormset+snmpling algorithm and coreset+exhaustive algorithm. In particular, on datasets containing more than 5000 input lines, our algorithm runs at least 43 times faster while maintaining or improving clustering quality. Furthermore, the consistently low standard deviation observed across all experiments demonstrates the robustness of our algorithm.
5 Conclusions
In this paper, propose the first local search algorithm for the k-means of lines problem, based single-swap strategy, which achieves a (500 + ->aaprooximtio guarantee and runs polynomial time for low-dimensional Euclidean space. To handle the lack of triangle inequality and the geometric complexity of line clustering, we design two core components: a proportional capture relation for aligning optimal and current centers, and a CrossLine structure for discretizing line interactions. Extensive experiments on both synthetic and real-world datasets demonstrate that our algorithm consistently outperforms coreset-based baselines in both efficiency and clustering quality. However, our current theoretical analysis and experimental evaluation are mainly limited to low-dimensional settings, and alleviating the d-dependence will be an interesting direction for future work.
Acknowledgments and Disclosure of Funding
This work was supported by the National Natural Science Foundation of China (Nos. 62432016 66 62172446) and the Central South University Research Program of Advanced Interdisciplinary Studies (No. 2023QYJC023). This work was also carried out in part using computing resources at the High Performance Computing Center of Central South University.
10

---

References
[1] Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive sampling for k-means clus- tering. In Proceedings of the 12th International Workshop Approximation Algorithms for Combinatorial Optimization, pages 15-28, 2009.
[2] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4):17-97, 2019.
[3] David Arthur and Sergei Vassilvitskii. k-means++ the advantages of careful seeding. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1027- 1035, 2007.
[4] Davin Choo, Christoph Grunau, Julian Portmann, and Václav Rozhoö. k-means++ few more steps yield constant approximation. In Proceedings of the 37th International Conference on Machine Learning, pages 1909-1917, 2020.
[5] Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Improved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In Proceedings of the 54th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1621-1628 2022.
[6] Vincent Cohen-Addat Philip N Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. SIAM Journal on Computing, 48(2):644-667, 2019.
[7] Zachary Friggstad, Mohsen Rezapour, and Mohammad R Salavatipour. Local search yields PTAS for k-means in doubling metrics. SIAM Journal on Computing, 48(2):452-480, 2019.
[8] Jie Gao, Michael Langherg, and Leonard J Schulman. Analysis of incomplete data and an intrinsic-dimension helly theorem. Discrete & Computational Geometry, 40:537-560, 2008.
[9] Jie Gao, Michael Langberg, and Leonard J Schulman. Clustering lines in high-dimensional space: Classification of incomplete data. ACM Transactions on Algorithms (TALG), 7(1):1-26, 2010.
[10] Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard Schulman, and Rakesh Venkat.
A refined approximation for euclidean k-means. Information Processing Letters, 176:106255
2022.
[11] Pierre Hansen, Jack Brimberg, Dragan Urošević, and Nenad Mladenovié. Solving large p- median clustering problems by primal-dual variable neighborhood search. Data Mining and Knowledge Discovery, 19:351-375, 2009.
[12] George TS Ho, WH Ip, Carman KM Lee, and WL Mou. Customer grouping for better resources allocation using GA based clustering technique. Expert Systems with Applications, 39(2):1979 1987, 2012.
[13] Junyu Huang, Qilong Feng, Ziyun Huang, Jinhui Xu, and Jianxin Wang. FL.S: new local search algorithm for k-means with smaller search space. In Proceedings of the 31 International Joint Conference on Artificial Intelligence, pages 3092-3098, 2022.
[14] Junyu Huang, Qilong Feng. Ziyun Huang, Jinhui Xu, and Jianxin Wang. Linear time algorithms for k-means with multi-swap local search. In Proceedings the 37th International Conference on Neural Information Processing Systems, pages 45651-45688 2023.
[15] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. Journal of the ACM, 57(2):1-32, 2010.
[16] Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In Proceedings of the 36th International Conference on Machine Learning, pages 3662-3671, 2019.
11

---

[17] Stuart Lloyd. Least squares quantization in PCM. IEEE transactions on information theory, 28(2):129-137, 1982.
[18] Sagi Lotan, Ernesto Evgeniy Sanches Shayda, and Dan Feldman. Coreset for line-sets clustering. Proceedings of the 35th International Conference on Neural Information Processing Systems, 11337333337777 2022.
[19] Konstantin Makarychev, Aravind Reddy, and Liren Shan. Improved guarantees for k-means++ and k-means++ parallel. In Proceedings of the 34th International Conference Neural Information Processing Systems, pages 16142-16152, 2020.
[20] Yair Marom and Dan Feldman. k-means clustering of lines for big data. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 12817-12826. 2019.
[21] Jifí Matoušek. On approximate geometric k-clustering. Discrete & Computational Geometry, 24(1):61-88) 2000.
[22] Björ Ommer and Jitendra Malik. Multi-scale object detection by clustering lines. In Proceed- ings of the 12th International Conference on Computer Vision, pages 484-491, 2009.
[23] Wei Pan, Xiaotong Shen, and Binghui Liu. Cluster analysis: unsupervised learning via su- pervised learning with a non-convex penalty. The Journal of Machine Learning Research, 14()):1865-188, 2013.
[24] Tomer Perets. Clustering of lines. Open University of Israel Ra anana, Israel, 2011.
[25] Rollet, GB Benie, W Li, S Wang, and JM Boucher. Image classification algorithm based on the rbf neural network and k-means. International Journal of Remote Sensing, 19(15):3033-3099
1998.
[26] Dennis Wei, constant- factor bi-criteria approximation guarantee for k-means++. In Proceed- ings of the 30th International Conference Neural Information Processing Systems, pages 004, 2016.
12

---

A The Missing Proof
A.1 Proof of Lemma 2
Lemma 2. Given an instance I I= (L, d, k) of the k-ML problem, let C' be the set of points returned by step 2 of MLS-K-ML. Then. for a finite constant p. we have ALL, C) p C*).
Proof. Let C* = (gi...., J denote the optimal solution of I. For any l E L, let a E and c" E C* denote the closest centers to l in C' and C*, respectively. Then, we have
(Vo(e,c") + Vo(Te(C),((T((()) + volc,e)) 2
A(L,C) Σ tEL
8(1,c) S
Σ
IEL
Σ
(Vo(e,c") 2(()((²*)
BEL
"(e,c") + +45(c,c)) + 4v
BEL
$ Σ (5((,c") + c,(c,c'),
REL
where the first inequality follows from triangle inequality, the second step follow from the fact that the distance between the projections of two points onto a line is at most their original Euclidean distance, and the last step follows the squared inequality and Cauchy inequality, respectively. Based on the Theorem in [24], the optimal solution to the k-means of lines problem can be obtained by selecting centers from the set of all pairwise line intersections (in IR2). Since the maximum pairwise distance between any two points in the candidate set P can be explicitly computed, we have ALL, C*) S p AL, C*), where p is a constant. Moreover, the initial solution can be obtained in O(nad²) time, constructing the candidate set P takes On))d²) time and sampling k centers from P takes ((1) time.
A.2 Proof of Lemma
Lemma 4. For any c E Cs (or e E Cx), the reassignment cost (c(c) (or nz(c)) is at most (A(I(C) + 24A(L(c), C*).
Proof. We first consider a type-1 match swap pair (c, (s(c) (c E Cs), as the case of type-2 match swap pair is nearly identical and even simpler. Let c¹ (c)(c). By definition 2, have (c) = ([AAT(c") CMe)) A(TA ). C), since lines in clusters other than L(c) will still be assigned their current center. Consider a line l E ((c))[((e) and it is easy to get that l does not belong to the optimal cluster L(c*). Let oj (c) c²) denote the closet optimal center in C* from &. Then, construct a line l' that is the translation of l cj. and then find a point c, that is the closet center in C' to f. It is easy to get that cp & otherwise will remain assigned to its original center and no reassignment will be necessary. We now assign every lines in L(c) L(c") to Gp. and get an estimate for the cost of reassigning these lines. Figure 1(b)-cc) shows two configurations of l, c, cj. and Cp. From Figure 1(b), we have
(Voie.2)+Vblee
2 5(e,c)
m mc)c S
Σ (EL(O)((e")
(8ll, - -((,,)) (EL(C)
Σ
Σ (2V/(e.C)) + vo(e.e) 8(1,c)
2
2 x V22 o(l, 8(E,c)
Σ 45(C, + +2
2 x (4+
Σ
8(e, + 22 8(l,c),
(EL(E)(Le')
13

---

e
CP
l
Cp
Cg
L'
8
C2
P
(a)
(b)
(c)
Figure 1: Illustrations of Line Configurations in IR and Id.
where the first inequality follows from equidistance property of parallel lines and squared inequality, the second step follow from the fact that c, is the closet center in C' to f", and the last step follows from the Cauchy Inequality, respectively. From Figure I(c), we have
(2V0(e00)+ Vo((.0) - 6(l,c)
m (c) < Σ
Σ
(EL(C)((O")
(EL())MEe))
2 x /2x o((, o(t,c) Σ 40(L,))) +2/ tEL(e)\M(>))
Σ (4+ x 8(1, c)) + 22 8(L,c),
REMOMME))
where the first inequality follows the fact that 8(E, Cp) < 8(t, under the configuration of Fig-
ure I(c), the second steps and the last step follows from squared inequality and Cauchy Inequality. For the configurations of Figure 1(b)-(c), let À To Then (n(c) S (T)((c), C) + 24 C*).
The cases for type-2 match swap pair (c, wiw (c CN) are similar to the cases for type- match swap pair.
A.3 Proof of Lemma
Lemma 5. If3 EoEcs A(L(Us(e)).C C) ALL,C), then have Eeeosnog AlL(vs(c)), C)
1
A).
50
Proof. By Definition 3 and Lemma 4, we have
Σ
A(L(os())) C) S
Σ (c) +9. 100
21 A(L,0) A(L,C)+ T.
100
cECsnC
cECs
Based on the assumption that A(L, 2 500 t, we obtain Eeessnoy A(L(os(c)), ALL C.), and thus ExeCercy A(L(os(c), C) 2 3/4 A)L,C).
250
A.4 Proof of Lemma 6
Lemma 6. Let be a set of lines in Rdd, and let e, Rd be two points. Then, the total squared distance from the lines in L to satisfies: A(L, (c}) & 3|Z] ((c,e') + 6 ALL, (d)), where (LI, = Eier 8(E,o) c) and 8(E, d) denote the squared Fuclidean distance from line to point e, respectively.
14

---

Proof. For any point I2² and line é E Q, let Te(c) denote the projection of c on f. let c be center in C. We have
8(L,c) 3 Σ (Vo(e,c*) (e( + Vo(c,ct))
S
EEL
REL
(V8(L,+*)+ +2V0(c,c*))
REL
8(e,c") (llc))+A/Vl.))
KEL.
$
Σ (6, + -6(c,cc))
EEL
<3A(T, (c*}) + 6(T
where the first inequality follows from the triangle inequality, the second step follow from the fact that the distance between the projections two points onto a line is at most their original Euclidean distance, respectively.
A.5 Proof of Lemma
Lemma 7. Let Q be a set of lines in Rd, let C' S Rd be a set of k centers, and let e* be the optimal single center for Q. Assume there exists a subset R S Q with A RR C) 2 a-1 A(Q,(c") where = {e E Q o(l,c)) S 24
9. If the cost under C satisfies AQQ, C) 2 AQQ, {ct }) then
2 AQQ, {c
Q
Proof. Based on the Lemma 6, know that the closest center in C to e* has distance at least a-3 (Q, {c*}) as otherwise A(Q, C) < a {c) Hence, the distance of every lines in R
6QQ
to C' is at least
2
3
cost (c'])
cost {c*})
22 2/
[Q|
24
[Q]
where use that 2 9. Furthermore, by averaging get [R] 2 /QQ/22 which together with the inequality above implies the result.
Li
A.6 Proof of Lemma
Lemma 8. Let E and & be two intersecting lines in I2, and let r >> 0 be a constant. Then, for any point x within r r-CrossLine, there exists at least one grid point from CrossLine, (E1, E2) whose distance to x is at most
Proof. The 9 grid points defined in Cro,sLine,(41, (2) form regular 3 x 3 grid in a parallelogram arrangement. The lines in Li are equally spaced at distance r, and so are the lines in L2. Thus, the grid divides the local region around the intersection point into parallelogram cells, each defined by two adjacent lines from L; and two from L2. Any point æ within CrossLine, (E,, must lie in one of these parallelogram cells. Since each parallelogram has diameter (i.e., maximal corner-to-cenler distance) less than or equal to r, any point & must within distance of least one vertex of the cell, which is a grid point of CrossLine, inn,, (f1, f2). Hence, the lemma follows.
A.7 Proof of Lemma
Execros ((L((N(c),,) Excrrcy A(L(#x(e)). C) 1o2 C).
Lemma 9.
3 A(L,C), then have
15

---

Proof. Note that 5 By the Definition 5 and Lemma 4, we have
Σ
O(L(V)(C)).)
S2|Cx|
min N2(c)) + 9r + 100 eECy
ALL, C)
CECACS,CECK
1 AL C)
(c(c) + +
100
cECN
41
C), + 57T.
100
Based on the assumption that ALL, C) 2 500 7, obtain Eecores A(I((w(e)), S ALL, C) and thus EEECrCo, A(T((x(()) 50 . A(.T,C).
131
11
250
A.8
Proof of Lemma 10
Lemma 10. For any e E Cs for e E CN), the reassignment cost in (c) (or m2(c)) is at most + C*) (see Appendix A.8 for proof).
Proof. Similar to Rd, we also construct a line l' that is the translation of to ot, and then find point Cp that is the closet center in C' to f". We now assign every lines in L(c) (c)))((e) to cp, and get an estimate for the cost of reassigning these lines. From Figure 1(c), we have
(Vore.c) + vole.o))
2
m (n)c)= V E
(6(k,cp) -((ec))) S (EL(C)(Lee)
Σ
c((,c)
tEL(E)(L(e))
E
(2V((1CC)+ vo(e,c) - 8(1,c)
2 48(L, +2 ī .22 o(6, o(t,c)
E
(EL(E)L(C))
Σ (EL(c))M(>))
(4+ 8(e, (7) + 22 o(L,c),
where the first inequality follows from equidistance property of parallel lines and triangle inequality, the second step follow from the fact that Cp is the closet center in C' to f", and the last step follows from the Cauchy Inequality, respectively. For the configuration of Figure Icc), let À = To
1 Then
m (c) < 5 A(L(C) (4)(Lcc). C*). The cases for type-2 match swap pair (c, (c)( (c CN)
are similar to the cases for type-1 match swap pair. The lemma follows.
A.9 Proof of Lemma 11
Lemma 11. Let & and lg be two intersecting lines in IRd, and let r > 0 be a constant. Then, for any point within r- CrossLLine, there exists at least one grid point from CrossLine, (E1, E2) whose distance to x is at most r.
Proof. By construction, each L, contains 3d lines, generated by shifting 4 along all combinations of {-1,0, 1]dd at step size r along coordinate axes. This induces a discrete grid of intersection points, where each point lies at the intersection of one line from L1 and one from L2. The resulting grid forms a regular structure embedded within the union of two axis-aligned hypercubes of side length 2r, centered near common point x=" Since each axis-aligned hypercube is of side length 2r, the distance between adjacent grid points along any axis at most r, and each hypercube cell (in which grid points are located at vertices) has diameter at most Vd. r. Then, for any point x lying within the convex hull of the grid points (i.e., the r-CrossLine region), there exists hypercube cell that contains
x. By geometry of axisnel cubes, any point within such a cell lies within distance r from at least one of its 2d corners, all of which are grid points. Hence, the lemma follows.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the contributions of the paper, which proposes the first single-swap local search algorithm for the k-means lines problem, leveraging a novel proportional capture relation and CrossLine structure achieve (500 + apprroxximtio in polynomial time. see Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes].
Justification:
The limitations discussed in the last section of this paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: All theoretical results are stated with full assumptions, and complete proofs are provided in the main paper and supplementary material (see Section 3 and appendix). Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The paper provides sufficient experimental details to allow reproduction of the main results and validation of the conclusions.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
18

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The codes (including dataset generation and experimental code) are available upon request via email.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
public/guides weweee///ooeeuumiieceeee astriissionP iioooolicy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (httpa: / //nips.cooa wttppccccpppcccccceeceeeecccceee /egguiddes/oeSummiiiinn Cooeeubmiii ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental settings have been clearly stated in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In the experiment comparison results, each algorithm is executed 10 times on each dataset, and the average results reported as the final results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
19

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The paper provides sufficient details about the computational resources used.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and confirm that research complies fully. The paper does not involve human subjects, sensitive data, or applications with known dual-use or misuse risks.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This paper mainly focuses on the theoretical aspect of the k-means of lines problem. The primary purpose is to provide algorithmic insights, and we do not foresce any specific societal consequences related to the proposed method.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
20

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks about safeguards.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not any external assets such as datasets, models, or third-party code. Therefore, licensing considerations are not applicable.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
21

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi choode. . com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not introduce release any new assets such as datasets, models, or software code. Therefore, documentation for new assets not applicable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowdsourcing experiments or research with human subjects. Therefore, this question is not applicable.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve any research with human subjects, and therefore IRB or equivalent ethical approval is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
22

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This paper does not involve the use of large language models (LLMs) as part of the core research methodology. Therefore, declaration is necessary.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: / ips. /tteripp.cccooofeeeenceeee /ttpc//eeeeeenee//2/5/////////// for what should or should not be described.
23


Reviews:
[{"review_id": "2S0Lk1Qtph", "reviewer": "Reviewer_XmFp", "summary": "The paper introduces a local search (LS) algorithm for k-means clustering of lines, where the input are lines in R^d and the k centers are points and the sum of squared distances of the lines to their closest of the k points points are to be minimized. The problem is said to have \"received little attention in existing literature\".\n\nI find The motivation of the model is vague, and it seems the reverse case has received a lot more attention, where the input consists of (possibly noisy) points from a linear flat and the centers are linear flats trying to reconstruct the true subspaces in which the points lie. Also when considering lines as inputs, why would they extend infinitely instead of just line segments, which would be a special case of polygonal curves clustering?\n\nThe problem in extending existing LS algorithms (for k-means) to the lines setting is of technical nature. For instance the tringle inequality does not hold and this complicates tracking the cost changes when reassigning from approximate centers to optimal centers. To this end a novel technique called \"proportional capture relation\" is introduced that also accounts for the number of reassigned lines to avoid large cost increase.\n\nThe second technical problem is in finding candidate swap pairs which is solved by a centroid set construction from previous coreset work [22] and a grid construction around the point where a pair of lines crosses (or attains its smallest distance in high dimensions)\n\nAlthough everything is claimed to be polynomial time in several places even in the high dimensional setting, I found C^d dependences which are clearly exponential (for the Cross Line grid construction).\n\nOnce those technicalities are solved, the analysis follows pretty much verbatim to recent work [18] on local search for the standard k-means of points, and more classic work (I am not sure but the right reference that is missing might be Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility\nlocation problems. SIAM Journal on Computing, 33(3):544–562, 2004. )", "questions": "- perhaps the authors could comment on the motivation of clustering infinite lines with points, instead of the more established settings of (finite) line segments as in polygonal curve clustering, or clustering points with linear flats as in subspace clustering?\n\n- I would recommend to specify \"with polynomial time\" in Theorem 1\n\n- I find it confusing to read the \\delta(p,q) notation for the **squared** Euclidean distances. why not \\delta(p,q)^2 ? Or better |p-q|_2^2!!\n\n- in 3.1 could you explain why is the choice of the smallest distance between two lines good?\n\n- below Lemma 3 two mentions of [22] where it should be [18] ?!\n\n- definnition 6 and running time analysis: 9^d does not look very polynomial to me ?!", "limitations": "Limitatios section is very limited. I think noise-freeness is minor compared to the *real* limitations such as exponential d dependence, very high approximation factor etc...", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "*Strength*\n- local search helps in the new setting\n- simple algorithm\n\n*Weakness*\n- weak motivation\n- high dimension dependence (C^d)\n- bad approximation factor 500 in expectation (so 1500 with probability 2/3 ?)\n- analysis very close to existing local search literature\n- lots of typos", "was_revised": true, "final_justification": "The rebuttal and discussion have slightly improved my opinion about the originality and technical strength of this submission. Motivation-wise, the problem seems to have some niche applications and could still be strengthened in the intro. Assumptions and limitations should be discussed more clearly, in particular the high d-dependence and associated limitation to (low) constant dimensions. Additionally, some sort of dimension reduction could strengthen the paper, and the applicability beyond 2D or 3D. I also agree with another reviewer that the paper may be a better fit in the TCS or CG community. Overall, I increased my rating slightly to a \"4: Borderline accept\".", "rebuttal": "**W1&Q1: regarding weak motivation.**\n\nResponse: We appreciate the reviewer’s insightful question. Clustering infinite lines with points has background application in Computer Vision [1-2]. For example, in the scenario using multiple cameras to observe fixed objects, it can be viewed from the objects that each camera has directional observations (i.e., direction from camera to the object), and a set of infinite lines can be obtained by considering each camera with direction to the corresponding object. Obviously, clustering these infinite lines helps identify different objects and recover their locations, as infinite lines observing the same object tend to intersect at or near the object's location. \n\nThus, the motivation of clustering infinite lines with points is to estimate the locations of multiple latent objects, based on directional information collected from spatially different viewpoints.\n\nIn contrast, curve and subspace clustering use curves and linear subspaces as centers, which do not support precise localization of objects. Moreover, infinite lines naturally encode unbounded directional information, which cannot be captured by finite segments, curves, or subspaces used in curve and subspace clustering. \n\nIn revised version, we will expand the motivation by emphasizing its practical relevance and clarifying its distinction from existing clustering paradigms.\n\n**W2&Q6: regarding high dimension dependence.**\n\nResponse: We apologize for the confusion. For clustering and related problems, the running time are always related to the input size $n$, dimension $d$, and cluster numbers $k$. Especially, for many PTAS approximation algorithms, which are called polynomial time approximation, the parameters $d$ and $k$ appear in exponential form in running time. For example, $O(n(\\log n)^k\\epsilon^{-2k^2d})$ for $k$-means [3], $O(k\\epsilon^{-d}\\log^{2d+2}n)$ for $k$-means and $k$-median [4]. The reason that all those algorithms are called polynomial time approximation is based on the fact that the parameters $d$ and $k$ are assumed to be fixed constants. \n\nFor line-clustering problems, discretization and geometric covering methods are usually used to design algorithms with theoretical guarantees, which always results in the exponential dependence on parameter dimension $d$ and the number of centers $k$. Following the routine of designing PTAS for clustering problems, in our paper, we view the parameters $d$ and $k$ as fixed constants. Although we have $9^d$ in the running time, it is still polynomial time on input size $n$. \n\n**W3: bad approximation factor 500 in expectation (so 1500 with probability 2/3?)**\n\nResponse: Thanks for pointing out this. Local search has been applied extensively to solve clustering and related problems, and many of them get approximation guarantees in expectation (e.g., 509 in [5], over $10^9$ in [6], and over 2000 in [7]). In this paper, we apply local search to solve the $k$-means of lines problem. Following the routine in the literature, we analyze the approximation factor in expectation. We agree with the reviewer that based on Markov's inequality, with probability at least 2/3, the factor is 1500. Intuitively, line-clustering is much harder than $k$-means or $k$-median. However, our expected approximation factor 500 is much better than the results in [6,7]. \n\nAlthough our approximation factor in expectation seems not good enough, we conduct experiments to show  the performance of our algorithm (see Table 1). It can be seen that our local search algorithm achieves much better performance with a large reduction in running time. \n\nExperimental Setup: We give comparisons between our local search algorithm and the coreset-based method from [1] on both synthetic datasets (SYN1 with n=5000 d=10, and SYN2 with n=10000 d=5) and a real-world Open Street Map dataset (RE1 with n=476 d=2, and RE2 with n=418 d=2) used in [1].\nFor coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search.\nFor our algorithm, we design a sampling strategy that selects a subset of 100 points from CrossLine to improve computational efficiency.\nFor each dataset, we run both algorithms 10 times and report minimum cost, maximum cost, and average cost, the standard deviation, and the runtime.\n\nTable 1: Experimental results of our algorithm and the coreset-based method.\n|Dataset|Method|$k$|Min_cost|Max_cost|Mean_cost|Std|time|\n|-|-|-|-|-|-|-|-|\n|RE1|Ours|10|**8.37E-10**|**1.72E-06**|**1.01E-07**|**2.73E-07**|**1.05**|\n|RE1|Coreset+sampling|10|8.17E-04|3.08E-02|6.24E-03|5.89E-03|6.05|\n|RE1|Coreset+exhaustive search|10|-|-|-|-|Over 12 hours|\n|RE1|Ours|3|**5.67E-06**|**1.15E-03**|**1.35E-04**|**2.00E-04**|**0.71**|\n|RE1|Coreset+sampling |3|1.57E-02|8.78E-01|1.39E-01|1.95E-01|4.08|\n|RE1|Coreset+exhaustive search |3|1.10E-03|2.11E-03|1.56E-03|3.01E-04|93.97|\n|RE2|Ours|10|**1.35E-08**|**3.16E-05**|**1.60E-06**|**4.66E-06**|**1.40**|\n|RE2|Coreset+sampling|10|2.89E-03|1.20E-01|2.16E-02|2.13E-02|3.34|\n|RE2|Coreset+exhaustive search |10|-|-|-|-|Over 12 hours|\n|RE2|Ours|3|**1.45E-05**|**5.59E-03**|**1.39E-03**|**1.18E-03**|**0.43**|\n|RE2|Coreset+sampling|3|4.88E-02|6.11E+00|6.21E-01|1.08E+00|4.91|\n|RE2|Coreset+exhaustive search|3|4.69E-04|4.83E-03|2.51E-03|1.09E-03|2.59E+02|\n|SYN1|Ours|10|**1.84E+04**|**1.88E+04**|**1.86E+04**|**1.97E+02**|**4.56E+02**|\n|SYN1|Coreset+sampling|10|3.97E+04|4.51E+04|4.24E+04|2.70E+03|2.04E+04|\n|SYN1|Coreset+exhaustive search|10|-|-|-|-|Over12 hours|\n|SYN2|Ours|3|**1.87E+04**|**1.98E+04**|**1.98E+04**|**5.45E+02**|**1.15E+03**|\n|SYN2|Coreset+sampling|3|-|-|-|-|Over 12 hours|\n|SYN2|Coreset+exhaustive search|3|-|-|-|-|Over 12 hours|\n\n**W4: analysis very close to existing local search literature.** \n\nResponse: We thank the reviewer for the comment. The local search has been applied to solve many clustering related problem, such as $k$-means [5-7], $k$-means with outlier [8-9], fair-range clustering [10]) or its related problems (e.g., subset selection [11]). It can be seen that the algorithm of applying local search always contains several routine steps, and seems similar for different problems. The major obstacle of local search is how to analyze the relation between local optimal solution and optimal solution, how to construct the swap pairs, and how to analyze the success probability, etc. It can be seen from [8-11] that for different problems, the theoretical guarantee analysis challenge may be totally different. \n\nFor line-clustering problem, the analysis of our local search process contains the following obstacles: (1) triangle inequality cannot be applied for point-to-line distance, which poses a big challenge for local search analysis; (2) it is difficult to identify effective swap points in infinite geometric space. \n\nBecause of the above obstacles, it is a non-trivial task to apply local search to solve the line-clustering problem. As far as we know, there is no available local search-based results in literature. To overcome these obstacles, in this paper, we propose a new method, called proportional capture relation, to bypass the triangle inequality barrier, and present a new structure, called CrossLine, to ensure the coverage of high-quality swap points for local search.\n\n**Q2: I would recommend to specify \"with polynomial time\" in Theorem 1.**\n\nResponse: We thank the reviewer for the helpful suggestion. In revised version, we will explicitly state that the algorithm runs in polynomial time with respect to the input size $n$, under the assumption that the dimension $d$ is treated as a fixed constant.\n\n**Q3: regarding the squared Euclidean distances.**\n\nResponse：Thanks for pointing this out. In revised version, we will replace the current notation with the more standard form $|p-q|_2^2$ to enhance clarity and consistency.\n\n**Q4: in 3.1 could you explain why is the choice of the smallest distance between two lines good?**\n\nResponse：Thanks for raising this question. In Section 3.1, we select the pair of lines with the smallest mutual distances, as this leads to an initial solution with an approximation guarantee. This conclusion is based on a key property given in Lemma 16 of [1]: Let $P$ be the candidate point set (i.e., the point set from the pair of lines with the smallest mutual distance). Then, selecting any $k$ points from $P$ suffices to approximate the optimal solution within a large constant factor. In local search, an initial solution with an approximation guarantee is critical, as the lack of such a guarantee can lead to excessive iterations and render the overall optimization process difficult to analyze.\n\n**Q5: below Lemma 3 two mentions of [22] where it should be [18]?!**\n\nResponse: We agree with the reviewer that both citations of [22] below Lemma 3 are incorrect, and should have referred to [18]. We will correct all those in revised version.\n\n[1]Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019.\n\n[2]Lotan S, Sanches Shayda E E, Feldman D. Coreset for line-sets clustering. NeurIPS 2022.\n\n[3]Matousek J. On approximate geometric $k$-clustering. Discrete & Computational Geometry 2000.\n\n[4]Har-Peled S, Mazumdar S. On coresets for $k$-means and $k$-median clustering. STOC 2004.\n\n[5]Lattanzi S, Sohler C. A better $k$-means++ algorithm via local search. ICML 2019.\n\n[6]Choo D, Grunau C, Portmann J, et al. $k$-means++: few more steps yield constant approximation. ICML 2020.\n\n[7]Fan C, Li P, Li X. LSDS++: Dual sampling for accelerated $k$-means++. ICML 2023. \n\n[8]Huang J, Feng Q, Huang Z, et al. Near-linear time approximation algorithms for $k$-means with outliers. ICML 2024.\n\n[9]Grunau C, Rozhon V. Adapting $k$-means algorithms for outliers. ICML 2022.\n\n[10]Zhang Z, Chen X, Liu L, et al. Parameterized approximation schemes for fair-range clustering. NeurIPS 2024.\n\n[11]Zou Y, Huang Z, Xu J, et al. Linear time approximation algorithm for column subset selection with local search. NeurIPS 2024."}, {"review_id": "K5vATLKssZ", "reviewer": "Reviewer_jhQS", "summary": "The paper addresses the problem of clustering a set of lines using points as cluster centers and the k-means objective. The idea is to develop an approximation algorithm in the framework of local swaps. The main difficulty is that the point-to-line distance, used in the paper, does not satisfy the triangle inequality, and thus standard local-swap arguments are not amenable to this setting. Another question to address for the method to be operational is the initialization step, for initializing cluster centers, before the local-swap phase. The paper proposes a new algorithm that addresses those questions and demonstrates that the proposed algorithm achieves a constant factor approximation in this local-swap setting. The paper is of mostly theoretical nature and there is no experimental evaluation of the proposed method.", "questions": "I welcome answers to weak points W1 and W2 mentioned above.", "limitations": "The authors make an honest attempt to list the limitations of their problem setting. In addition to the ones listed by the authors, I would also add the weak points mentioned above.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The main strengths of the paper are the clarity in the problem definition, the rigorous analysis of the proposed method, and the achievement of obtaining a constant-factor approximation for the problem of clustering lines. \nOn the other hand, I found a few important weaknesses. \nW1. I found the motivation of the problem very weak. The paper states as motivation applications in traffic and motion data analysis. However, such real-world data are never straight (infinite lines). Another element missing motivation is the choice of using points as cluster centers. Why not using lines as cluster centers? This looks a more straightforward generalization of the k-means setting for points, where both the data and the cluster centers are points. Overall, I am totally on board that the problem is intellectually interesting and a meaningful generalization of the k-means problem for points, however, I think that for a AI/ML conference like NeurIPS a stronger motivation is needed. Perhaps the paper is a better fit for a venue in theoretical computer science, or computational geometry.\nW2. Earlier work provides a PTAS for the same problem, while this paper provides a constant-factor approximation, with a very large constant. Thus, this is not the theoretically best result available. Indeed, the claim of the paper is that this is the first constant-factor approximation for the local-swaps setting, not for the problem itself. It is also true that the PTAS algorithm has high complexity. However, to strengthen the value of the paper as a practical alternative with manageable complexity I would expect to see some experimental evaluation of the proposed method. Additionally, a convincing experimental evaluation would also address the issue of motivation in real-world applications, by forcing the authors to identify meaningful datasets and applications to use the lines-clustering problem and methods. Overall, I appreciate the contribution of \"first constant-factor approximation within a specific solution framework\" and I value the technical depth and rigorous analysis of the paper, however, in addition to the weak motivation, and lack of experimental evaluation, I think that the overall contribution is not sufficient for NeurIPS.", "was_revised": true, "final_justification": "The paper addresses an intellectually interesting problem and the technical novelty is good, however, I still see a number of weaknesses. In particular, (i) the problem motivation is weak; (ii) the theoretical running time of the method is large; (iii) the theoretical approximation guarantee is large; and (iv) the theoretical improvement is only for a particular family of methods (local search) and it is not general. Another weakness is that the paper originally did not contain any experimental evaluation. The authors provided some experimental results in the rebuttal. My concern is whether providing (the complete set of) experiments in the rebuttal phase goes beyond the scope of what a rebuttal is meant to be. Additionally, there is the issue of fairness to the authors of other submissions. This could be discussed among the area chair and the other reviewers. Overall, given these weakesses and concerns, I am keeping my original score to \"borderline reject\".", "rebuttal": "**W1. I found the motivation of the problem very weak. The paper states as motivation applications in traffic and motion data analysis. However, such real-world data are never straight (infinite lines). Another element missing motivation is the choice of using points as cluster centers. Why not using lines as cluster centers? This looks a more straightforward generalization of the k-means setting for points, where both the data and the cluster centers are points. Overall, I am totally on board that the problem is intellectually interesting and a meaningful generalization of the k-means problem for points, however, I think that for a AI/ML conference like NeurIPS a stronger motivation is needed. Perhaps the paper is a better fit for a venue in theoretical computer science, or computational geometry.**\n\nResponse: We appreciate the reviewer’s insightful question. Clustering infinite lines with points can be naturally applied to the following scenarios in motion data analysis [1]: in multi-camera systems that observe 3D dynamic objects in complex scenes, each camera provides a directional observation toward an object (i.e., a ray extending from the camera to the observed object.) By representing each such observation as an infinite line in space, a set of lines corresponding to different views can be obtained. Obviously, clustering these infinite lines helps identify different objects and recover object locations, as infinite lines observing the same object tend to intersect at or near the object’s location. Thus, the motivation of clustering infinite lines with points centers is to estimate the locations of multiple latent objects, based on directional information collected from spatially different viewpoints. \n\nAlthough real-world data are not truly straight or infinite lines, for the multi-camera systems observing 3D dynamic objects, any directional measurement from a fixed viewpoint to an object can be naturally modeled as an infinite line in space. Under those applications, it is reasonable to model the observations as infinite lines. Obviously, for the observation object applications, all the views can be modeled as infinite lines.\n\nFor the multi-camera systems observing objects application, since infinite lines observing the same object tend to intersect at or near the object’s location, it is natural to use point as centers to clustering infinite lines. Moreover, since the infinite lines have unbounded nature, if an infinite line is chosen as center, inferring precise object locations in Euclidean space seems not workable. \n\nIn the revised version of the paper, we will clearly present the motivation by emphasizing its practical relevance.\n\n**W2. Added experimental evaluation.**\n\nResponse: We thank the reviewer for pointing this out. For completeness, we give comparisons between our local search algorithm and the coreset-based method from [2] on both synthetic datasets and a real-world Open Street Map dataset used in [2]. \n\nWe give comparisons between our local search algorithm and the coreset-based method from [2] on both synthetic datasets (SYN1 with $n$=5000, $d$=10, and SYN2 with $n$=10000, $d$=5) and a real-world Open Street Map dataset used in [2]. \nFor the Open Street Map dataset, we follow [2] and obtain two road dataset: RE1 ($n$=476, $d$=2) and RE2 ($n$=418, $d$=2). \nFor the coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search.\nFor our algorithm in $\\mathbb{R}^d$, we design a sampling strategy that selects a subset of points from CrossLine to improve computational efficiency. \nThe number of samples is set to 100. For each dataset, we run both algorithms 10 times and report minimum cost, maximum cost, and average cost, the standard deviation, and the runtime.\n\nThe results show that our algorithms always achieve the best performance compared with coreset+sampling algorithm and coreset+exhaustive algorithm. In particular, on datasets containing more than 5000 input lines, our algorithm runs at least 43 times faster while maintaining or improving clustering quality.\n\nTable 1: Experimental results of our algorithm and the coreset-based method.\n\n|Dataset|Method|$k$|Min_cost|Max_cost|Mean_cost|Std|time|\n|-|-|-|-|-|-|-|-|\n|RE1|Ours|10|**8.37E-10**|**1.72E-06**|**1.01E-07**|**2.73E-07**|**1.05**|\n|RE1|Coreset+sampling|10|8.17E-04|3.08E-02|6.24E-03|5.89E-03|6.05|\n|RE1|Coreset+exhaustive search|10|-|-|-|-|Over 12 hours|\n|RE1|Ours|3|**5.67E-06**|**1.15E-03**|**1.35E-04**|**2.00E-04**|**0.71**|\n|RE1|Coreset+sampling |3|1.57E-02|8.78E-01|1.39E-01|1.95E-01|4.08|\n|RE1|Coreset+exhaustive search |3|1.10E-03|2.11E-03|1.56E-03|3.01E-04|93.97|\n|RE2|Ours|10|**1.35E-08**|**3.16E-05**|**1.60E-06**|**4.66E-06**|**1.40**|\n|RE2|Coreset+sampling|10|2.89E-03|1.20E-01|2.16E-02|2.13E-02|3.34|\n|RE2|Coreset+exhaustive search |10|-|-|-|-|Over 12 hours|\n|RE2|Ours|3|**1.45E-05**|**5.59E-03**|**1.39E-03**|**1.18E-03**|**0.43**|\n|RE2|Coreset+sampling|3|4.88E-02|6.11E+00|6.21E-01|1.08E+00|4.91|\n|RE2|Coreset+exhaustive search|3|4.69E-04|4.83E-03|2.51E-03|1.09E-03|2.59E+02|\n|SYN1|Ours|10|**1.84E+04**|**1.88E+04**|**1.86E+04**|**1.97E+02**|**4.56E+02**|\n|SYN1|Coreset+sampling|10|3.97E+04|4.51E+04|4.24E+04|2.70E+03|2.04E+04|\n|SYN1|Coreset+exhaustive search|10|-|-|-|-|Over12 hours|\n|SYN2|Ours|3|**1.87E+04**|**1.98E+04**|**1.98E+04**|**5.45E+02**|**1.15E+03**|\n|SYN2|Coreset+sampling|3|-|-|-|-|Over 12 hours|\n|SYN2|Coreset+exhaustive search|3|-|-|-|-|Over 12 hours|\n\n[1] Zhang T, Chen X, Wang Y, et al. MUTR3D: A multi-camera tracking framework via 3D-to-2D queries. CVPR 2022.\n\n[2] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019."}, {"review_id": "R5CyxLsOcX", "reviewer": "Reviewer_XTPN", "summary": "This paper studies the $k$-means of lines problem. Compared to the original $k$-means problem, the dataset $P$ consists of $n$ lines rather than points. The algorithm needs to find $k$ centers $C \\subset \\mathbb{R}^d$ to minimize $\\sum_{p\\in P}\\min_{c\\in C}d(p,c)^2$, where $d(p,c)$ denotes the distance between line $p$ and point $c$. \n\nThis paper proposes the first local search algorithm (with a theoretical guarantee) for the $k$-means problem. Local search is widely used for designing efficient clustering algorithms. However, it is hard to generalize the local search algorithms for the original $k$-means problem to the line setting, since the geometric properties of lines are very different from points. \n\nIn order to overcome the challenges, the authors introduce a new mapping between the current solution and the optimal solution. \nThey also designed a new sampling procedure which discretizes the solution space into a finite set of representative points so that they can sample candidate centers efficiently.", "questions": "See weakness.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strength:\n\n1. This paper proposes the first constant-approximate algorithm for the $k$-means problem in polynomial time. In order to apply local search to the $k$-means of lines problem, the authors develop several new techniques to overcome the complicated geometric properties of lines. These techniques may also be used in the following studies of $k$-means of lines or even other geometric problems. \n\n2. Their algorithm is quite simple and efficient in practice (in low-dimensional cases). \n\nWeakness:\n\nThe running time of the algorithm has an exponential dependency on $d$, which means the algorithm might not be polynomial time in high-dimensional cases.", "was_revised": true, "final_justification": "The authors explain the hardness of the problem, which answers my question in weakness.", "rebuttal": "**Question：The running time of the algorithm has an exponential dependency on $d$, which means the algorithm might not be polynomial time in high-dimensional cases.**\n\nResponse: We apologize for the confusion. For clustering and related problems, the running time are always related to the input size $n$, dimension $d$, and cluster numbers $k$. Especially, for many PTAS approximation algorithms, which are called polynomial time approximation, the parameters $d$ and $k$ appears in exponential form in running time. For example, $O(n(\\log n)^k\\epsilon^{-2k^2d})$ for $k$-means [1], $O(k\\epsilon^{-d}\\log^{2d+2}n)$ for $k$-means and $k$-median [2]. The reason that all   those algorithms are called polynomial time approximation is based on the fact that the parameters $d$ and $k$ are assumed to be fixed constants. \n\nFor the line-clustering problems, discretization and geometric covering methods are usually used to design algorithms with theoretical guarantees, which always results in the exponential dependence on parameter dimension $d$ and the number of centers $k$. Following the routine of designing PTAS for clustering problem, in our paper, we view the parameters $d$ and $k$ as fixed constants. Although we have $9^d$ in the running time, it is still polynomial time on input size $n$.\n\nMoreover, we conduct experiments to illustrate our algorithm performance (see Table 1). It can be seen that our proposed local search algorithm achieves much better performance with a large reduction in running time.   In particular, on datasets containing more than 5000 input lines, our algorithm runs at least 43 times faster while maintaining or improving clustering quality.\n\nExperimental Setup: We give comparisons between our local search algorithm and the coreset-based method from [3] on both synthetic datasets (SYN1 with $n$=5000, $d$=10, and SYN2 with $n$=10000, $d$=5) and a real-world Open Street Map dataset used in [3]. \nFor the Open Street Map dataset, we follow [3] and obtain two road dataset: Region 1 ($n$=476, $d$=2) and Region 2 ($n$=418, $d$=2). \nFor the coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search.\nFor our algorithm in $\\mathbb{R}^d$, we design a sampling strategy that selects a subset of points from CrossLine to  improve computational efficiency.\nThe number of samples is set to 100. For each dataset, we run both algorithms 10 times and report minimum cost, maximum cost, and average cost, the standard deviation, and the runtime.\n\nTable 1: Experimental results of our algorithm and the coreset-based method.\n|Dataset|Method|$k$|Min_cost|Max_cost|Mean_cost|Std|time|\n|-|-|-|-|-|-|-|-|\n|RE1|Ours|10|**8.37E-10**|**1.72E-06**|**1.01E-07**|**2.73E-07**|**1.05**|\n|RE1|Coreset+sampling|10|8.17E-04|3.08E-02|6.24E-03|5.89E-03|6.05|\n|RE1|Coreset+exhaustive search|10|-|-|-|-|Over 12 hours|\n|RE1|Ours|3|**5.67E-06**|**1.15E-03**|**1.35E-04**|**2.00E-04**|**0.71**|\n|RE1|Coreset+sampling |3|1.57E-02|8.78E-01|1.39E-01|1.95E-01|4.08|\n|RE1|Coreset+exhaustive search |3|1.10E-03|2.11E-03|1.56E-03|3.01E-04|93.97|\n|RE2|Ours|10|**1.35E-08**|**3.16E-05**|**1.60E-06**|**4.66E-06**|**1.40**|\n|RE2|Coreset+sampling|10|2.89E-03|1.20E-01|2.16E-02|2.13E-02|3.34|\n|RE2|Coreset+exhaustive search |10|-|-|-|-|Over 12 hours|\n|RE2|Ours|3|**1.45E-05**|**5.59E-03**|**1.39E-03**|**1.18E-03**|**0.43**|\n|RE2|Coreset+sampling|3|4.88E-02|6.11E+00|6.21E-01|1.08E+00|4.91|\n|RE2|Coreset+exhaustive search|3|4.69E-04|4.83E-03|2.51E-03|1.09E-03|2.59E+02|\n|SYN1|Ours|10|**1.84E+04**|**1.88E+04**|**1.86E+04**|**1.97E+02**|**4.56E+02**|\n|SYN1|Coreset+sampling|10|3.97E+04|4.51E+04|4.24E+04|2.70E+03|2.04E+04|\n|SYN1|Coreset+exhaustive search|10|-|-|-|-|Over12 hours|\n|SYN2|Ours|3|**1.87E+04**|**1.98E+04**|**1.98E+04**|**5.45E+02**|**1.15E+03**|\n|SYN2|Coreset+sampling|3|-|-|-|-|Over 12 hours|\n|SYN2|Coreset+exhaustive search|3|-|-|-|-|Over 12 hours|\n\n\n\n\n\n\n\n[1] Jirı Matousek. On approximate geometric $k$-clustering. Discrete & Computational Geometry, 2000.\n\n[2] Har-Peled S, Mazumdar S. On coresets for $k$-means and $k$-median clustering. STOC 2004.\n\n[3] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019."}, {"review_id": "hggbXycImL", "reviewer": "Reviewer_n7xV", "summary": "This paper addresses the $k$-means clustering problem, where the input objects are lines in Euclidean space rather than points. The authors propose a 500-approximation algorithm using a local search framework, which is adapted in a non-trivial way to handle the geometric and analytical challenges posed by clustering lines.\n\nThe algorithm proceeds in two main steps:\n1. Initialization via coreset: It begins with a coreset-based algorithm from [Marom and Feldman (2019)], originally developed for the $k$-median of lines. Although this coreset was designed for a different objective, the authors show that it yields a constant-factor approximation for the $k$-means of lines problem—though the precise approximation ratio is not specified.\n2. Local search: The solution is then improved using a standard local search approach—specifically, center swapping—adapted to the line setting. The candidate centers are constructed by sampling two lines with probability proportional to their current cost and creating a fine grid near their intersection point. This process is repeated a polynomial number of times.\n\nA major analytical challenge is that a single line can be simultaneously close to multiple centers, even if those centers are far apart from each other, making it difficult to directly apply the triangle inequality. Furthermore, since centers can be located anywhere in continuous space, the analysis requires careful discretization.\n\nThe high-level argument behind the approximation guarantee is that if the current solution is significantly worse than the optimum (e.g., more than 500× the optimal cost), then there’s a good chance that the weighted-sampled lines will be close to optimal centers. If these lines are near the same optimal center, then their intersection is a promising candidate for placing a new center. This allows the algorithm to iteratively improve the solution by exploring neighborhoods around such intersections.", "questions": "### Major comments\n- Assumption on non-parallel lines: The paper assumes all input lines are pairwise non-parallel. In practical settings (e.g., road networks, trajectories), parallel lines are common. Is there a simple extension of your algorithm to handle such inputs?\n- Radius parameter in CrossLine structure: The definition relies on a radius $r$ tied to the optimal cost, which is unknown in practice. How is $r$ chosen algorithmically? Can it be estimated in a data-dependent or iterative way?\n- Candidate center construction: Lemma 8 suggests that optimal centers are near intersections of two nearby lines. Since there are only $O(n^2)$ such intersections, could you simply use all of them as candidate centers for classical point-based local search? Would this simplify the algorithm or analysis?\n\n### Minor comments\n- Line 67–68: The description appears to misrepresent paper [9].\n- Line 70–72: The summary of paper [10] does not seem accurate.\n- Line 200–202: Citation [22] does not pertain to local search.\n- Line 211: “near to $c^*$” → “near $c^*$”\n- Line 210–213: The claim about the failure of capture relations in the line setting is not entirely clear. A visual counterexample would help clarify this point.\n- Line 231–237: Regarding type-2 matched swap pairs: if a center $c$ captures no optimal centers, you pair it with an optimal center “borrowed” from a richer center $c’$. What becomes of $c’$—is it then a type-1 or type-2 pair? This edge case deserves clarification.\n- Line 250 (Definition 2): Please clarify the notion of “reassignment cost”—is this just an upper bound on the cost increase when removing a center?\n- Lines 110, 270, 274, 292: Typo—“closed to” → “close to”\n- Line 292: The inequality $\\Delta(L(\\psi_S(c)),C) \\geq 9\\cdot \\Delta (L(\\psi_S(c)),\\{\\psi_S(c)\\})$ based on Definition 3 is not immediately obvious. Please expand on how Definition 3 implies this bound.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strength\n- This is the first constant-factor approximation algorithm for the $k$-means of lines problem with an explicit approximation ratio.\n- It successfully adapts the local search technique to this geometric setting, which involves non-trivial modifications and theoretical insights.\n\n### Weakness\n- The analysis, especially the main proof, is difficult to follow. Breaking it down into smaller, modular lemmas and including more illustrative diagrams would significantly improve readability.\n- Due to the complexity and density of the arguments, I was not able to fully verify all parts of the analysis. While the general structure seems plausible, a more accessible presentation would increase confidence in the result.", "was_revised": true, "final_justification": "The authors have addressed all my questions. After reading all rebuttal-response histories, I decide to keep my current score.", "rebuttal": "**Major comments：**\n\n**Question 1.\tAssumption on non-parallel lines: The paper assumes all input lines are pairwise non-parallel. In practical settings (e.g., road networks, trajectories), parallel lines are common. Is there a simple extension of your algorithm to handle such inputs?**\n\nResponse to reviewer: Thanks for raising this question. In our paper, the assumption that all input lines are non-parallel is made primarily for analytical convenience. Indeed, our algorithm naturally extends to inputs that include parallel lines, and the quality of the solution remains largely unaffected. There are two cases to consider: (1) When all input lines are mutually parallel, each line can be projected onto an axis orthogonal to their common direction, thereby reducing the original problem to a 1-median problem over points in one-dimensional space. For this case, we simply check whether all lines are parallel and, if so, solve the resulting 1-median problem on $\\mathbb{R}$.  (2) If the input contains at least one non-parallel lines pair, all optimal cluster centers can be selected from the set of pairwise intersections of the input lines in $\\mathbb{R}^2$ [1], or near the candidate point set returned by Algorithm 2 in higher dimensions [2]. Therefore, we simply skip parallel line pairs in Step 4 of Algorithm 2 and Step 4 of Algorithm 1.\n\n**Question 2.\tRadius parameter in CrossLine structure: The definition relies on a radius r tied to the optimal cost, which is unknown in practice. How is chosen algorithmically? Can it be estimated in a data-dependent or iterative way?**\n\nResponse to reviewer: We thank the reviewer for pointing this out. Since the radius $r$ in the CrossLine structure is defined in terms of the (unknown) optimal cost for theoretical analysis, we choose $r$ in practice using a data-driven iterative heuristic. This choice is based on the observation that if $r$ is too small, the optimal center may lie outside the constructed CrossLine, thereby failing to ensure that at least one point is sufficiently close to the optimal center. Conversely, an excessively large radius may cause all points returned by the CrossLine structure to lie far from the optimal center, resulting in failed single-swap steps. Motivated by Lemma 8, which states that the optimal center lies near the intersection of two nearby lines, we iteratively expand the radius around the intersection. Specifically, we start from a small initial radius (e.g., 0.1 times the minimum distance between the intersection to the point set returned by CrossLine) and iteratively increase it by a fixed step size until the swap succeeds or the radius reaches a predefined upper bound (e.g., the minimum distance between the intersection to the point set returned by CrossLine).\n\n\n**Question 3.\tCandidate center construction: Lemma 8 suggests that optimal centers are near intersections of two nearby lines. Since there are only such intersections, could you simply use all of them as candidate centers for classical point-based local search? Would this simplify the algorithm or analysis?**\n\nResponse to reviewer: We thank the reviewer for this thoughtful question. While these intersections are geometrically meaningful, we cannot simply use all of them as candidate centers for classical point-based local search, since the algorithm optimizes point-to-point distances rather than point-to-line distances, which are fundamentally different in the line clustering setting. Specifically, if classical point-based local search is directly applied to all intersection points, the optimization focuses on minimizing distances between intersections and centers, rather than between lines and centers. Since a line may yield multiple intersections with other lines, point-based local search may assign these intersections to different centers, leading to ambiguity in determining which center the line should be associated with. Therefore, applying all intersections to a classical point-based local search algorithm does not simplify the algorithm or the analysis.\n\n\n**Minor comments：**\n\n**Question 1.\tLine 67–68: The description appears to misrepresent paper [9].**\n\nResponse：We appreciate the reviewer for raising this point. We apologize for this misrepresentation and will correct the statement in the revised version to accurately reflect the contributions of [9].\n\n**Question 2.\tLine 70–72: The summary of paper [10] does not seem accurate.**\n\nResponse：Thank you for pointing this out. We apologize for the inaccurate summary and will correct the description in the revised version to more accurately reflect the contributions of [10].\n\n**Question 3.\tLine 200–202: Citation [22] does not pertain to local search.**\n\nResponse: We thank the reviewer for pointing this out. Upon careful verification, we agree that citation [22] was mistakenly cited in this context and does not relate to local search. The correct reference should be [18], which provides the relevant analysis of the local search algorithm for classical point-based clustering. We will revise the manuscript accordingly to ensure accurate attribution.\n\n\n**Question 4. Line 211: \"near to $c^*$ → \"near $c^*$\"**\n\nResponse: Thank you for pointing out the grammatical errors. We will correct these issues in the revised version and perform a thorough proofreading of the full paper.\n\n**Question 5.\tLine 210–213: The claim about the failure of capture relations in the line setting is not entirely clear. A visual counterexample would help clarify this point.**\n\nResponse: Thank you for the suggestion. We agree that the explanation was not sufficiently clear. In the revised version, we will include a simple visual counterexample to illustrate why the capture relation may fail in the line setting due to directionality and angular differences.\n\n**Question 6.\tLine 231–237: Regarding type-2 matched swap pairs: if a center captures no optimal centers, you pair it with an optimal center “borrowed” from a richer center c’. What becomes of—is it then a type-1 or type-2 pair? This edge case deserves clarification.**\n\nResponse: Thanks for raising this question. We state that this case still corresponds to a type-2 matched pair, since according to the definition of proportional capture relation, the borrowed optimal center is not captured by the center $c'$, i.e., the  borrowed optimal center does not receives the largest fraction of lines from that center. We will clarify this point in the revised version.\n\n**Question 7.\tLine 250 (Definition 2): Please clarify the notion of “reassignment cost”—is this just an upper bound on the cost increase when removing a center?**\n\nResponse: Thanks for raising this question. We state that the \"reassignment cost\" of Definition 2 is simply an upper bound on the increase in clustering cost when a center is removed, and we will clarify this explicitly in the revised version.\n\n**Question 8.\tLines 110, 270, 274, 292: Typo \"closed to\" → \"close to\"**\n\nResponse: We appreciate the reviewer for pointing out these typographical errors. We will correct these typos in the revised manuscript.\n\n**Question 9.\tLine 292: The inequality based on Definition 3 is not immediately obvious. Please expand on how Definition 3 implies this bound.**\n\nResponse: We thank the reviewer for pointing this out. We acknowledge that there was a notation error in Definitions 3 and 5 regarding the characterization of good type-1 and type-2 clusters. These definitions are intended to be consistent with those in [3], and we will correct the presentation accordingly in the revised version. \nFormally, we state that for any $c \\in C_S$ , the cluster $L(c)$ is a good type-1 cluster if \n\n$\\Delta(L(\\psi_S(c)),C)-\\eta_1(c)-9\\Delta(L(\\psi_S(c)),\\{\\psi_S(c)\\})>\\frac{1}{100k}\\Delta(L,C)$. \n\nA good type-2 cluster is defined analogously. Based on the corrected definitions, we observe that the reassignment cost $\\eta_1(c)$ is non-negative, and thus the inequality in Line 292 follows directly.\n\n[1] Tomer Perets. Clustering of lines. Open University of Israel, 2011.\n\n[2] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019.\n\n[3] Lattanzi S, Sohler C. A better $k$-means++ algorithm via local search. ICML 2019."}, {"review_id": "njDQmzw0Kv", "reviewer": "Reviewer_N5Cm", "summary": "The paper introduces an algorithm for clustering lines into k sets. The method is reminiscent of K-means++, but instead of sampling centers from a distribution, the authors discretize the continuous space using a grid and search over a finite set of candidate points. The theoretical analysis is solid and provides meaningful guarantees. I didn’t go through every proof in detail, but the parts I did check seemed correct, and the overall reasoning appears sound.\n\nOne limitation is the absence of numerical experiments—not even simple ones on synthetic data. While the authors mention that the method isn’t expected to be robust to noise, it would still be helpful to see the algorithm in action to better understand its behavior. The paper is clearly written, and although it’s more theoretical than most NeurIPS submissions, I think it’s a worthwhile contribution. That said, theory papers can be difficult to fully evaluate under conference reviewing timelines, and small technical issues might go unnoticed.", "questions": "Could you explain why you chose not to include any numerical experiments?\nEven basic examples—successful or not—would help make the paper more accessible to a broader audience.", "limitations": "Lack of empirical evaluation.\nThe analysis is based on idealized data, with no consideration for noise, although this is addressed in the discussion.\nPotential sensitivity to initialization or local optima is not addressed.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n>Clear and well-organized theoretical analysis.\n>Tackles a relatively unexplored problem.\n>The algorithm design is interesting and non-trivial.\n\nWeaknesses:\n>No experimental validation.\n>No discussion of robustness or practical performance.", "was_revised": true, "final_justification": "The paper presents a theoretical analysis of a k-means-for-lines algorithm. While the algorithm itself appears simple, it is both novel and interesting. The work is entirely theoretical, which was somewhat surprising; however, on request, the authors provided numerical results that met my original expectations. I believe the paper is stronger as a theory-only contribution, so I would not recommend including these results in the camera-ready version—though they could be a useful addition to the supplementary material.\n\nAlthough I generally prefer to see applications alongside theory, I appreciate the authors’ clear and accessible exposition within the NeurIPS formatting constraints. Their approach emphasizes explanation over impressiveness for its own sake, which is commendable. Discussions with other reviewers and the authors’ rebuttal have reinforced my positive impression. I am therefore leaning towards acceptance.", "rebuttal": "**Weakness and Question: No experimental validation. Could you explain why you chose not to include any numerical experiments? Even basic examples—successful or not—would help make the paper more accessible to a broader audience. No discussion of robustness or practical performance.**\n\nResponse to reviewer: Thanks for raising this question.  We initially focused on establishing theoretical guarantees and approximation bounds for the $k$-means of lines problem based on the local search algorithm. Moreover, we fully agree that numerical experiments can greatly enhance the accessibility and practical relevance of our results. In response to this suggestion, we include a set of numerical experiments as follows.\n\nExperimental Setup: We give comparisons between our local search algorithm and the coreset-based method from [1] on both synthetic datasets (SYN1 with $n$=5000, $d$=10, and SYN2 with $n$=10000, $d$=5) and a real-world Open Street Map dataset used in [1]. \nFor the Open Street Map dataset, we follow [1] and obtain two road dataset: Region 1 ($n$=476, $d$=2) and Region 2 ($n$=418, $d$=2). \nFor the coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search.\nFor our algorithm in $\\mathbb{R}^d$, we design a sampling strategy that selects a subset of points from CrossLine to improve computational efficiency.\nThe number of samples is set to 100. For each dataset, we run both algorithms 10 times and report minimum cost, maximum cost, and average cost, the standard deviation, and the runtime.\n\nThe results show that our algorithms always achieve the best performance compared with coreset+sampling algorithm and coreset+exhaustive algorithm.  In particular, on datasets containing more than 5000 input lines, our algorithm runs at least 43 times faster while maintaining or improving clustering quality. Furthermore, the consistently low standard deviation observed across all experiments demonstrates the robustness of our algorithm.\n\nTable 1: Experimental results of our algorithm and the coreset-based method.\n\n|Dataset|Method|$k$|Min_cost|Max_cost|Mean_cost|Std|time|\n|-|-|-|-|-|-|-|-|\n|RE1|Ours|10|**8.37E-10**|**1.72E-06**|**1.01E-07**|**2.73E-07**|**1.05**|\n|RE1|Coreset+sampling|10|8.17E-04|3.08E-02|6.24E-03|5.89E-03|6.05|\n|RE1|Coreset+exhaustive search|10|-|-|-|-|Over 12 hours|\n|RE1|Ours|3|**5.67E-06**|**1.15E-03**|**1.35E-04**|**2.00E-04**|**0.71**|\n|RE1|Coreset+sampling |3|1.57E-02|8.78E-01|1.39E-01|1.95E-01|4.08|\n|RE1|Coreset+exhaustive search |3|1.10E-03|2.11E-03|1.56E-03|3.01E-04|93.97|\n|RE2|Ours|10|**1.35E-08**|**3.16E-05**|**1.60E-06**|**4.66E-06**|**1.40**|\n|RE2|Coreset+sampling|10|2.89E-03|1.20E-01|2.16E-02|2.13E-02|3.34|\n|RE2|Coreset+exhaustive search |10|-|-|-|-|Over 12 hours|\n|RE2|Ours|3|**1.45E-05**|**5.59E-03**|**1.39E-03**|**1.18E-03**|**0.43**|\n|RE2|Coreset+sampling|3|4.88E-02|6.11E+00|6.21E-01|1.08E+00|4.91|\n|RE2|Coreset+exhaustive search|3|4.69E-04|4.83E-03|2.51E-03|1.09E-03|2.59E+02|\n|SYN1|Ours|10|**1.84E+04**|**1.88E+04**|**1.86E+04**|**1.97E+02**|**4.56E+02**|\n|SYN1|Coreset+sampling|10|3.97E+04|4.51E+04|4.24E+04|2.70E+03|2.04E+04|\n|SYN1|Coreset+exhaustive search|10|-|-|-|-|Over12 hours|\n|SYN2|Ours|3|**1.87E+04**|**1.98E+04**|**1.98E+04**|**5.45E+02**|**1.15E+03**|\n|SYN2|Coreset+sampling|3|-|-|-|-|Over 12 hours|\n|SYN2|Coreset+exhaustive search|3|-|-|-|-|Over 12 hours|\n\n\n\n[1] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019."}]

Author rebuttal:

Meta-review: The authors study the k-means on line problem that is a natural extension of the classic k-means problem and captures many natural scenarios.

In particular, they propose a local search algorithm to obtain a poly time approximation algorithm for the problem.

The committee found the problem and the results interesting, although few  improvements should be implemented before publication:
- the paper contains multiple typos that should be fixed.
- the experiments should be included in the final version of the paper.
- a longer discussion on the practical motivation of the paper should be added to the paper.
Decision: Accept (poster)