A Single-Swap Local Search Algorithm for k-Means of Lines

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.

Response 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.

Experimental 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]. For 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). For the coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search. For our algorithm in $\mathbb{R}^d$, we design a sampling strategy that selects a subset of points from CrossLine to improve computational efficiency. The 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.

The 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.

Table 1: Experimental results of our algorithm and the coreset-based method.

[1] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019.

Major comments：

Question 1. 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?

Response 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.

Question 2. Radius 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?

Response 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).

Question 3. Candidate 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?

Response 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.

Minor comments：

Question 1. Line 67–68: The description appears to misrepresent paper [9].

Response：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].

Question 2. Line 70–72: The summary of paper [10] does not seem accurate.

Response：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].

Question 3. Line 200–202: Citation [22] does not pertain to local search.

Response: 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.

Question 4. Line 211: "near to $c^*$ → "near $c^*$"

Response: 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.

Question 5. 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.

Response: 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.

Question 6. Line 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.

Response: 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.

Question 7. 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?

Response: 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.

Question 8. Lines 110, 270, 274, 292: Typo "closed to" → "close to"

Response: We appreciate the reviewer for pointing out these typographical errors. We will correct these typos in the revised manuscript.

Question 9. Line 292: The inequality based on Definition 3 is not immediately obvious. Please expand on how Definition 3 implies this bound.

Response: 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. Formally, we state that for any $c \in C_S$ , the cluster $L(c)$ is a good type-1 cluster if

$\Delta(L(\psi_S(c)),C)-\eta_1(c)-9\Delta(L(\psi_S(c)),\{\psi_S(c)\})>\frac{1}{100k}\Delta(L,C)$.

A 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.

[1] Tomer Perets. Clustering of lines. Open University of Israel, 2011.

[2] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019.

[3] Lattanzi S, Sohler C. A better $k$-means++ algorithm via local search. ICML 2019.

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.

Response: 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.

For 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$.

Moreover, 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.

Experimental 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]. For 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). For the coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search. For our algorithm in $\mathbb{R}^d$, we design a sampling strategy that selects a subset of points from CrossLine to improve computational efficiency. The 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.

Table 1: Experimental results of our algorithm and the coreset-based method.

[1] Jirı Matousek. On approximate geometric $k$-clustering. Discrete & Computational Geometry, 2000.

[2] Har-Peled S, Mazumdar S. On coresets for $k$-means and $k$-median clustering. STOC 2004.

[3] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019.

W1&Q1: regarding weak motivation.

Response: 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.

Thus, 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.

In 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.

In revised version, we will expand the motivation by emphasizing its practical relevance and clarifying its distinction from existing clustering paradigms.

W2&Q6: regarding high dimension dependence.

Response: 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.

For 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$.

W3: bad approximation factor 500 in expectation (so 1500 with probability 2/3?)

Response: 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].

Although 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.

Experimental 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]. For coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search. For our algorithm, we design a sampling strategy that selects a subset of 100 points from CrossLine to improve computational efficiency. For each dataset, we run both algorithms 10 times and report minimum cost, maximum cost, and average cost, the standard deviation, and the runtime.

Table 1: Experimental results of our algorithm and the coreset-based method.

W4: analysis very close to existing local search literature.

Response: 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.

For 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.

Because 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.

Q2: I would recommend to specify "with polynomial time" in Theorem 1.

Response: 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.

Q3: regarding the squared Euclidean distances.

Response：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.

Q4: in 3.1 could you explain why is the choice of the smallest distance between two lines good?

Response：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.

Q5: below Lemma 3 two mentions of [22] where it should be [18]?!

Response: 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.

[1]Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019.

[2]Lotan S, Sanches Shayda E E, Feldman D. Coreset for line-sets clustering. NeurIPS 2022.

[3]Matousek J. On approximate geometric $k$-clustering. Discrete & Computational Geometry 2000.

[4]Har-Peled S, Mazumdar S. On coresets for $k$-means and $k$-median clustering. STOC 2004.

[5]Lattanzi S, Sohler C. A better $k$-means++ algorithm via local search. ICML 2019.

[6]Choo D, Grunau C, Portmann J, et al. $k$-means++: few more steps yield constant approximation. ICML 2020.

[7]Fan C, Li P, Li X. LSDS++: Dual sampling for accelerated $k$-means++. ICML 2023.

[8]Huang J, Feng Q, Huang Z, et al. Near-linear time approximation algorithms for $k$-means with outliers. ICML 2024.

[9]Grunau C, Rozhon V. Adapting $k$-means algorithms for outliers. ICML 2022.

[10]Zhang Z, Chen X, Liu L, et al. Parameterized approximation schemes for fair-range clustering. NeurIPS 2024.

[11]Zou Y, Huang Z, Xu J, et al. Linear time approximation algorithm for column subset selection with local search. NeurIPS 2024.

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.

Response: 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.

Although 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.

For 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.

In the revised version of the paper, we will clearly present the motivation by emphasizing its practical relevance.

W2. Added experimental evaluation.

Response: 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].

We 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]. For the Open Street Map dataset, we follow [2] and obtain two road dataset: RE1 ($n$=476, $d$=2) and RE2 ($n$=418, $d$=2). For the coreset-based method, we compress the data with their coreset algorithm and select $k$ centers via sampling or exhaustive search. For our algorithm in $\mathbb{R}^d$, we design a sampling strategy that selects a subset of points from CrossLine to improve computational efficiency. The 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.

The 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.

Table 1: Experimental results of our algorithm and the coreset-based method.

[1] Zhang T, Chen X, Wang Y, et al. MUTR3D: A multi-camera tracking framework via 3D-to-2D queries. CVPR 2022.

[2] Marom Y, Feldman D. $k$-Means clustering of lines for big data. NeurIPS 2019.