acceptodds
Under review as a conference paper at ICLR 2027

Boundary Detection for High-Dimensional Point Clouds

Abstract

We introduce two new methods for boundary detection in high-dimensional point cloud data, intended to work in situations with non-uniform density, high ambient dimension, and substantial noise. Our first method fits a separating hyperplane on local neighborhoods after doing local dimension reduction—this method works best when one can reliably estimate the intrinsic dimension of the data. Our second method measures the directional uniformity of local neighborhoods, and has the best overall performance on synthetic data. In addition to pointwise numerical boundary scores, our algorithms yield an estimated normal vector at each boundary point. We validate our methodology on synthetic data as well as two real examples: we analyze spatial transcriptomics data, where we show that we can detect the boundary of a tumor, and we also study LLM activation geometry.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
geometric data analysis, boundary detection

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Z1WmOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies boundary detection in high-dimensional point clouds and proposes a hyperplane method and a directional uniformity method. The former finds a hyperplane that keeps as many neighboring points as possible on one side, while the latter examines whether the neighborhood directions are uniform. Experiments show that the proposed methods outperform existing methods when the density is non-uniform, the ambient dimension is high, and noise is present.

Critical strengths
  1. The proposed methods are highly innovative and effectively address the problem that existing methods rely on density.

2.Experimental results show that the proposed method is more stable than existing geometric methods under high ambient dimensions and noise, and can also provide normals. This strongly demonstrates the effectiveness of the method.

Critical weaknesses

1.Although the results on synthetic data are relatively good, there is a lack of quantitative comparative experiments and metrics on real data, which raises doubts about the practicality of the method.

Questions for authors
  1. It is suggested to add quantitative experiments on real data.

2.When the true intrinsic dimension is unknown, how should one choose between the hyperplane method and the directional uniformity method? When spectral gap estimation of the dimension fails, the hyperplane method may mistake a noise-thickened surface for a boundary. Beyond post-hoc comparison, is there an automatic criterion that does not rely on the true dimension?

3.On real data, do high scores actually correspond to the boundaries claimed by the authors? For example, in spatial transcriptomics, what proportion of the high-scoring points come from the outer edge of the tissue section versus the mesenchymal-like–proliferative-like transition, respectively?

1 comment

We thank the reviewer for taking the time to review our paper, and we appreciate the positive remarks about the effectiveness of our method.

Response to weaknesses:

We have clarified in our revision that both the spatial transcriptomics data set and the LLM data have ground truth boundaries. As we wrote in response to reviewer #1:

“For the real-world spatial transcriptomics data set, a very good proxy for the ground-truth tumor boundary is the mesenchymal/proliferative contrast, shown in Figure 10 (left). The tumor boundary is where this contrast is close to zero. We explain this more clearly in our revision. We emphasize the our boundary detection methods did not use the the mesenchymal/proliferative contrast. For the character counting manifold, the ground truth boundary is {(i, w) s.t. i = 0 or i = w or w = 15 or w = 150}, where i = character position and w = line width. We show in Figure 11d that our detected boundary largely agrees with the ground truth.”

Response to questions:

Q1: Thank you for this feedback. See our response above.

Q2: One criterion is to check for pointwise consistency of the dimension estimates. If the pointwise dimension estimates are not consistent with each other, then this is a strong indication that one does not have an accurate dimension estimate. In that case, we suggest using the directional uniformity method.

Q3: We clarify that the boundary points near the tissue edge can be ignored because one can visually see that these high-scoring points are on the tissue boundary.

Reviewer_TBJGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents two methods for boundary detection of high-dimensional point clouds, HP (Hyperplane) and DU (Directional Uniformity). The main idea of HP is that for boundary points, a hyperplane can be fit s.t. most of the kNN lie on one side of the hyperplane and that this distribution is different from points that lie within a point cloud. The main idea of DU is to regard the direction vectors to its neighbors' projection onto a sphere: if they are rather uniformly distributed, the point lies within a manifold or point cloud, else it is a boundary point, which is quantified with a boundary score. The method is compared to BEPS (Border Edge Pattern Selection, Li& Maguire, 2011) and LoDD (Peng et al., 2025) on some synthetic datasets and two real world datasets: a spatial transcriptomics data with two different cell-states and an character-counting manifold.

Critical strengths

S1) Visually, the methods achieve their goals and detect the boundaries of the manifolds well.

S2) Both methods are intuitive and explainable.

Critical weaknesses

W1) Related work is limited

  • The concept of boundaries or border points is existing in different research areas that have been overlooked here. Specifically, the relation to the following methods should be discussed: LOF (Local Outlier Factor) [1], border points in the context of clustering, e.g. from DBSCAN [2] and ABC [3], as well as other boundary detection methods, e.g. [4,5]

[1] Breunig, M. M., Kriegel, H. P., Ng, R. T., & Sander, J. (2000, May). LOF: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data (pp. 93-104).

[2] Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd (Vol. 96, No. 34, pp. 226-231).

[3] Beer, A., Seeholzer, D., Schüler, N. S., & Seidl, T. (2020, September). Angle-based clustering. In International Conference on Similarity Search and Applications (pp. 312-320). Cham: Springer International Publishing.

[4] Liu, D., Nosovskiy, G.V., Sourina, O.: Effective clustering and boundary detection algorithm based on Delaunay triangulation. Pattern Recogn. Lett. 29(9), 1261–1273 (2008)

[5] Moreira, A., Santos, M.Y.: Concave hull: a k-nearest neighbours approach for the computation of the region occupied by a set of points (2007)

W2) Experiments

  • The manifolds tested look rather convex. It would be interesting to see how the methods behave on non convex manifolds with arbitrary shapes. Especially in those, the choice of the hyperparameter k might be crucial.
  • Ablation experiments on k (neighborhood size) should be included. Most experiments simply use k=100 or k=200 - how does this depend on a) the dataset size, b) the intrinsic dimensionality, and c) the convexity of the manifold?
  • Including more than two competitors would draft a clearer picture of when/why to use these methods, see above for some ideas for references.
  • Motivation of real-world experiments should be improved (see questions below)

W3) Clarification on goal/motivation could be improved

  • It would be helpful to have quantitative proof of the quality of results. For that, one would need meaningful, existing ground truth datasets. Are those existing? If not, where will your method be applied? E.g., for the experiment in Fig. 6, I do not see why the results of LoDD or BEPS should be considered worse than the results of HP and DU - it surely depends on the use case. So why is it important to not detect all border points, but only the ones at the ends of the line segments?

Minor

  • Clarify when to use which of your two methods more clearly.
  • Fig. 5b is referenced even though there is no a) or b) in Fig. 5.
  • Theorem 2.1 and 2.2: use \varepsilon instead of \epsilon for mathematical variables
  • Font size in some figures is too small, e.g. in Fig. 8
  • Order of methods tested is sometimes mixed up (e.g. Fig. 14 vs Fig. 15 in the appendix), keep it uniform.
Questions for authors

Q1) In Sec. 5, wouldn't it be more helpful to simply apply clustering to the data and find the two different regions? That would give more information than 'only' knowing where the border between the two groups is.

Q2) What is the use case of finding the boundary of the LLM activation geometry?

Q3) How do your scores related to classic border points as known from clustering?

5 comments
AuthorsOpenReview ↗

Rebuttal to weakness #1

We thank the reviewer for suggesting these additional comparisons and other additional experiments.

We emphasize, in light of the reviewer’s second comment, that our original manuscript already included comparisons with more than two methods. In our first synthetic data experiment (see Table 1 and Figure 13), we compared against 7 other methods (now 9 in the revision) on a data set with non-uniform sampling density. Five of these (now 6 in the revision) did poorly, so due to space constraints, we focused the remaining experiments on the two (now three in the revision) leading competitors (LoDD and BEPS, and now [3] in the revision). In the Related Works section, we discussed the limitations of two (now four in the revision) additional methods that are only designed for 2D data. In total, our original manuscript included nine other competitors and the revised version now includes 13. Most of the competitors in the original manuscript are methods from the clustering literature.

We have revised the Related Works section and the synthetic data section to include the suggested papers, except for [2] (see explanation below):

[1] is a density-based method that is primarily designed for outlier detection, a related but slightly different problem than boundary detection. It does poorly on our non-uniform density example. We have added it to Table 1 and Figure 13, and we have added a sentence about it in the first paragraph of our Related Works section.

[2] is the paper for DBSCAN, which introduces the notion of “border” and “core” points but does not give a definition for “border” points, so we did not add it to our paper. We note that the goal of [2] is clustering, not boundary detection.

[3] is a boundary detection method that measures the one-sidedness of local neighborhoods. We have added it to all our synthetic experiments. Unlike most other methods in the literature, it is capable of handling non-uniform sampling density. However, it struggles with high ambient dimension and high noise, like BEPS. Additionally, for non-convex examples, it does significantly worse than DU (ours), HP (ours), LoDD, and BEPS. We quantify this using AUC values.

[4] and [5] are only practical for low ambient dimensions because they involve Delaunay triangulation and computing the concave hull, respectively. We have added a brief discussion of [4] and [5] to our Related Works section.

AuthorsOpenReview ↗

Rebuttal to weakness #2

  • Our original manuscript included six non-convex subsets of Euclidean space, but we have added two additional examples (concentric rings and nested moons). Additionally, we added AUC values for the non-convex examples so that we can quantify each method’s performance. See Figures 3 and 5 in the main text and Figures 15 and 20 in the appendix. Non-convexity generally does not pose an issue because boundary point neighborhoods on a non-convex manifold still look like a uniformly sampled half ball, just like our other examples. Although convexity does not seem to matter, the reach of the manifold does. For accurate boundary detection, the neighborhood size should not be much larger than the reach of the manifold. This is a fundamental limitation of most methods in geometric data analysis. Our revision includes neighborhood size ablation experiments for all non-convex data sets, in Figure 16 in the appendix.

  • We added additional ablation experiments on neighborhood size. See our response to the first reviewer (vURZ) for a more detailed discussion. Additionally, Theorems 2.1 and 2.2 tell us something about how the neighborhood size should scale with intrinsic dimension.

  • We note that our original manuscript included comparisons with seven competitors, not two. In the Related Works section, our original paper also discussed two additional competitors that only work in low ambient dimension. In the revised manuscript, we have added two additional competitors ([1] and [3]) to the synthetic experiments, and we have added a discussion of [4] and [5] to the Related Works section. Methods [4] and [5] are not included in the experiments because they can only be used for low-dimensional data. We excluded DBSCAN [2] because it is a clustering paper that does not provide an explicit method for detecting boundary points, even though it does talk broadly about the idea of “core” and “border” points.

  • In response to the question below about clustering for the spatial transcriptomics data, we added a figure showing the results of k-means clustering. When we run k-means on the point cloud Y that we used for boundary detection (i.e., exact same preprocessing), the clusters do not correspond to the tumor / non-tumor region at any choice of k (number of clusters), even k = 2. The highest silhouette score is at k = 3. We also tested different preprocessing choices where we varied a scaling factor alpha in [0, 1] for the spatial and gene coordinates. At alpha = 0 and alpha = .2 with k = 2 clusters, k-means is able to extract the tumor region. However, one does not know a priori that these are the correct alpha values. At other alpha and k values, k-means is not successful at extracting the tumor region, and k = 2 is not always the highest silhouette score. In our own methods, varying the neighborhood size parameter changes the smoothness of the boundary scores, but it does not drastically change the result. (See Figure 26 in the appendix.)

AuthorsOpenReview ↗

Rebuttal to weakness #3

In our synthetic experiments, the point clouds are sampled from known manifolds with known boundaries. We used those ground-truth boundaries to quantify and compare the performance of the boundary detection algorithms. For the line segments, we note that the only boundary points of a line segment are its endpoints. The other points are not boundary points of a 1D line segment.

For our spatial transcriptomics and LLM point clouds, we have good proxies for the ground-truth boundaries. As we wrote in response to reviewer #1:

“For the real-world spatial transcriptomics data set, a very good proxy for the ground-truth tumor boundary is the mesenchymal/proliferative contrast, shown in Figure 10 (left). The tumor boundary is where this contrast is close to zero. We explain this more clearly in our revision. We emphasize the our boundary detection methods did not use the the mesenchymal/proliferative contrast. For the character counting manifold, the ground truth boundary is {(i, w) s.t. i = 0 or i = w or w = 15 or w = 150}, where i = character position and w = line width. We show in Figure 11d that our detected boundary largely agrees with the ground truth.”

Reviewer_vURZOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes two training-free boundary scores for high-dimensional point clouds. HP measures one-sided neighborhood occupancy after local PCA, while DU measures alignment of local directional resultants. The paper provides an idealized analysis of HP and evaluates the methods on synthetic data, spatial transcriptomics, and LLM activations.

Critical strengths
  • The methods are intuitive, straightforward, and require no training.
  • Selected synthetic experiments show promising results, and the HP analysis offers some justification under idealized sampling conditions.
Critical weaknesses
  1. Insufficient methodological and theoretical justification. The connection between manifold boundaries, directional asymmetry, and application-specific transitions is not established. HP's theory relies on restrictive assumptions and contains unresolved proof issues, while DU remains heuristic. Close relationships to BEPS/CO and missing PCA-matched comparisons further leave the incremental contribution unclear.

  2. Insufficient empirical validation. Robustness to sampling conditions, neighborhood scale, and outliers is not systematically evaluated, while excluding transition regions from the main AUC protocol leaves precise localization insufficiently assessed. Real-world results remain largely qualitative, without sufficient independent annotations, baseline comparisons, or downstream validation to support broad applicability.

Questions for authors

No additional questions beyond the concerns above.

2 comments
AuthorsOpenReview ↗

Rebuttal to weakness #1

We thank the reviewer for reading our paper carefully and giving us feedback that we have used to revise our paper.

  • After receiving reviews, we checked the proofs using Claude, which surfaced some minor typos and errors. We have corrected these. The proofs and theorem statements have not substantively changed, except for the fact that Theorem 2.1 now has the additional assumption that the dimension must be n≥2n \geq 2 for our proof to hold. We believe that the statement is also true for n=1n = 1, but the proof as written does not directly show it. We are not aware of any major proof issues, but we would like to correct any errors, so we would appreciate if the reviewer would point out the specific issues that they are concerned about.

  • We are not sure what the reviewer means by “restrictive assumptions”. What we assume is that after local PCA, the neighborhood of a boundary/interior point on an n-dimensional manifold can be treated as a uniformly sampled n-dimensional half/full ball, respectively. We think this is reasonable because:

  1. At small enough scales, and ignoring curvature, local neighborhoods do look approximately like half/full balls because this is the topological definition of a boundary/manifold point, respectively. In a half space of R^n and in R^n itself (where curvature is zero), local neighborhoods are precisely half/full balls.
  2. We emphasize that our result does not require the entire point cloud to be a ball or half ball—only local neighborhoods, which aligns with how the hyperplane boundary score is computed.
  3. Our proof assumes that we have estimated the manifold dimension correctly because dimension estimation (a well studied problem in its own right) is outside the scope of our paper. This is standard across geometric data analysis papers.
  4. Assuming a continuous probability density function, density is approximately constant locally, even if the manifold as a whole is not sampled uniformly.

To clarify what we mean by a “boundary point”, we note that we are analyzing unlabeled point cloud data and we are aiming to detect topological boundaries. In topology, the definition of boundary (or interior) point is that it has a neighborhood that is homeomorphic to a Euclidean half ball (or full ball, respectively). We say this at the beginning of Section 2, where we introduce the hyperplane method. This is a fundamentally different set up from, for example, detecting the boundary between two classes in a labeled data set. In that case, our assumptions would be unreasonable (and generally untrue), but that is not the setting of our paper.

  • For DU, there is existing theory for the related Rayleigh uniformity test (mentioned briefly in our paper). In the future, we plan to adapt those results for the setting in our paper.

  • We have edited the Related Works section to explain that there is very little theory, in general, for boundary detection. To the best of our knowledge, LoDD is the only other method for high-dimensional data that comes with any theoretical guarantees about boundary detection, but their theorems are very limited. Their theorems only apply to 2D subsets of R^2, and they assume that neighborhood points, after being projected to the circle centered at the query point, are exactly evenly spaced, which is not realistic. In contrast, our results hold for manifolds with intrinsic dimension n >= 2, and we have more realistic sampling assumptions.

  • In spite of methodological similarities to BEPS/CO, our empirical performance improvement is profound. CO could not handle non-uniform density data, as shown by Table 1 and Figure 13 (appendix). BEPS could not handle high ambient dimensions, even with low noise, as seen in Figure 5 (surface embedded in R^15). These are fundamental weaknesses when one is analyzing real data. Furthermore, neither BEPS nor CO had any theoretical guarantees. We have edited the Related Work section to emphasize our improvements compared to BEPS and CO.

AuthorsOpenReview ↗

Rebuttal to weakness #2

  • In our first synthetic experiment, we tested non-uniform sampling density and found that our methods were robust to sampling density variation. We have added a synthetic experiment with outliers. For HP, DU, LoDD, and BEPS, outliers have little effect on the boundary scores of other points because (1) outliers are unlikely to be nearest neighbors of other points and (2) even if an outlier is part of a neighborhood, a single point out of k neighbors has a small effect on the boundary score.

  • We have added ablation experiments for the neighborhood scale parameter. In general, boundaries are correctly detected as long as

  1. The neighborhood scale parameter is within the range at which the dimension can be correctly estimated. This is a fundamental limitation across most geometric data analysis methods, and there are inherent ambiguities in dimension estimation. For example, if one samples from a 1D line segment in R^2 with noise (as we do in Figure 7), should that be considered a 1D object or a (thin) 2D object? At sufficiently large scales, it is 1D, but at small scales, the point cloud appears 2D. When the estimated dimension m is incorrect, we find that our methods correctly find the boundary of the objection when treated as an m-dimensional object, which is the best that one can hope for. See Figure 7, for example, where we sample from two line segments with noise. For the DU method, the neighborhood parameter can actually be smaller than the range at which dimension is correctly estimated (see Figure 7 again). See also Figure 19, which shows AUC scores for a disk embedded in R^D. This shows that the boundary is estimated correctly when k is sufficiently large so that dimension is accurate.

  2. The second requirement is that neighborhoods are not much larger than the reach of the manifold (the maximum radius r such that every point in the ambient space has a unique closest point on the manifold, e.g., for a circle the reach is its radius). This is, again, a limitation across most geometric methods. Our revision includes neighborhood size ablation experiments on non-covex synthetic data sets. See Figure 16.

  • For AUC scores, we have redefined our empirical definitions of “boundary” and “interior” point so that there are no excluded transition regions. Additionally, we added AUC values for the non-convex examples. For the majority of data sets (unless otherwise indicated), we define a point to be a boundary point if its distance the ground-truth boundary is less than r_k/2, where r_k is the point’s distance to its k nearest neighbor. It is an interior point otherwise. For the point clouds that are sampled from a disk and then embedded in R^D, we define r_k to be the maximum in-place distance to one of its kNNs, and we compare this to its in-plane distance to the boundary. The first experiment, where the data set has non-uniform density, is an exception. We are using the same boundary/interior definition as in the original manuscript. For this data set, we want to focus on the ability of each method to distinguish between unambiguous boundary points and the deep interior points. The deep interior points are a small fraction of the whole data set.

  • For the real-world spatial transcriptomics data set, a very good proxy for the ground-truth tumor boundary is the mesenchymal/proliferative contrast, shown in Figure 10 (left). The tumor boundary is where this contrast is close to zero. We explain this more clearly in our revision. We emphasize the our boundary detection methods did not use the the mesenchymal/proliferative contrast. For the character counting manifold, the ground truth boundary is {(i, w) s.t. i = 0 or i = w or w = 15 or w = 150}, where i = character position and w = line width. We show in Figure 11d that our detected boundary largely agrees with the ground truth.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.