betaFeedback

WorksComputer Science

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.

Introduction

The manifold hypothesis specifies that point cloud data is sampled from a distribution supported on a low-dimensional manifold. A natural variant of this setup is to assume that the support is instead a manifold with boundary. In this case, determining the location of the boundary and a normal vector to it become fundamental questions. Algorithms to determine the boundary have many applications. For example, in spatial transcriptomics data, each point on a grid has a gene expression vector that lies in Rn\mathbb{R}^{n} for nn approximately 20000. Detecting boundary regions in genomic space allow us to determine qualitative changes in underlying tissue, for example transitions from cancerous tumor regions to healthy cells. Another application of interest is to study the geometry of LLM activations. Recent mechanistic interpretability work has discovered that residual-stream activations often lie on curved submanifolds rather than linear subspaces [9, 7, 10, 3]. Model behavior can be influenced by adding a “steering” vector at intermediate activations (Turner et al., 2024; Panickssery et al., 2024), but these interventions work best when one is able to stay on the underlying manifold (Wurgraft et al., 2026). Knowing the boundary points as well as having estimated boundary normals is useful for steering interventions and other interpretability problems. More broadly, boundary detection can be used for general-purpose methods such as clustering [2] (Wang et al. 2018).

Contributions

We introduce two general-purpose methods for identifying boundary points and calculating normal vectors at the boundary. Both methods are fast and practical for large data sets. Our hyperplane method works the best among all tested methods when the local dimension can be reliably estimated. When the estimated dimension mm is larger than the true dimension, it finds the correct boundary of the data as though it were mm-dimensional. Our directional uniformity method is more robust when noise levels prevent accurate dimension estimates.

The hyperplane method is mathematically grounded by theorems proving that boundary points can be reliably distinguished from interior points in a way that scales well with intrinsic dimension. We empirically validate both methods on synthetic data.

Finally, we show that our methodology is effective on spatial transcriptomics data for identifying a tumor boundary, and we also apply it to find the boundary of LLM activations for the character-counting manifold of [10] for open-weight models.

We have released the source code and scripts for reproducing our figures and experiments on github: https://github.com/aghickok/boundary_detection.

Related Work

There are several boundary-detection methods that rely on the fact that boundary points have lower density than interior points. BORDER (Xia et al., 2006) counts the number of “reverse kk nearest neighbors” (RkNN\mathrm{RkNN}), i.e., the number of points for which the query point is a kkNN. Boundary points tend to have fewer kkNNs. Averbuch-Elor et al. [2] and Du et al. [6] also use reverse kkNNs for boundary detection, as an intermediate step towards clustering. In more detail, Averbuch-Elor et al. [2] and Du et al. [6] calculate ∑xj∈RkNN(xi)K(xi,xj)\sum_{x_j\in\mathrm{RkNN}(x_i)} K(x_i,x_j), where KK is a Gaussian or Cauchy kernel, respectively. Reverse unreachability (RU) [11] is different; it uses the representation matrix WW from Roweis & Saul (2000) to approximate each point xix_i as a linear combination ∑jWijxj\sum_j W_{ij}x_j of its neighbors, and then reverse unreachability is defined as ∑j1Wji≤0\sum_j \mathbf{1}_{W_{ji}\le0}. All of these methods perform poorly when the point cloud has non-uniform density.

Some methods are only designed to be used for very low-dimensional data. The direction centrality measure (Peng et al., 2022) is defined for data in R2\mathbb{R}^2 and the level-set method [5] was only applied to 2D data. Both methods can be theoretically generalized to higher dimensions, but scale poorly with ambient dimension and are not practical for data that is more than two dimensional.

The last class of methods uses geometric structure to detection boundaries in data of any dimension. Border Edge Pattern Selection (BEPS) [12], CO (Wang et al., 2018), and LoDD (Peng et al., 2025) all start by projecting the nearest neighbors {xij}\{x_{ij}\} to the unit sphere centered at the query point xix_i. Let yˉij:=(xij−xi)/∥xij−xi∥\bar{y}_{ij}:=(x_{ij}-x_i)/\lVert x_{ij}-x_i\rVert and define vˉi:=1k∑j=1kyˉij\bar{v}_i:=\frac{1}{k}\sum_{j=1}^{k}\bar{y}_{ij}. BEPS is similar to our hyperplane method—the BEPS score 1k∑j1yˉij⋅vˉi≥0\frac{1}{k}\sum_j\mathbf{1}_{\bar{y}_{ij}\cdot\bar{v}_i\ge0} is the percentage of neighbors on the positive side of the hyperplane orthogonal to vˉi\bar{v}_i. It is far less robust to noise than either of our methods, though, because the direction of the vector vˉi\bar{v}_i is sensitive to noisy perturbations off the manifold, especially on interior points where E[vˉi]=0\mathbb{E}[\bar{v}_i]=0.

The CO score (Wang et al., 2018) uses the same vector vˉi\bar{v}_i but scales by density and measures the alignment between neighbors. At query point xix_i, the score is ∑j=1kmi−1mj−1vˉi⋅vˉj\sum_{j=1}^{k}m_i^{-1}m_j^{-1}\bar{v}_i\cdot\bar{v}_j, where mi−1=∑j∥xij−xi∥m_i^{-1}=\sum_j\lVert x_{ij}-x_i\rVert is a “mass” term that is high in regions with low density. Like the other density-based methods, CO performs poorly on data with non-uniform density.

The LoDD score is ω(∑i=1dλi)2+(1−ω)2dd−1∑i∑j≠iλiλj\omega(\sum_{i=1}^{d}\lambda_i)^2+(1-\omega)\frac{2d}{d-1}\sum_i\sum_{j\ne i}\lambda_i\lambda_j, where {λi}\{\lambda_i\} is the set of eigenvalues of the covariance matrix for the centered, normalized neighbor vectors {yˉij}\{\bar{y}_{ij}\} and ω∈[0,1]\omega\in[0,1] is a hyperparameter that is set to .5 in Peng et al. (2025) and in our experiments in this paper. The LoDD score has a maximum of 1 that is achieved when the eigenvalues are equal and sum to 1. It is higher for interior points because {yˉij}\{\bar{y}_{ij}\} is uniformly distributed on the dd-dimensional sphere. LoDD has the strongest overall performance of all the existing methods we tested in the literature, but it is less robust than ours to noise, especially in high ambient dimensions. Unlike our methods (or BEPS or CO), LoDD does not produce normal vectors at each point—just pointwise boundary scores.

Hyperplane method for boundary detection

The idea of our hyperplane (HP) boundary-detection algorithm, detailed in Algorithm 1, is that if xx is a boundary point on an nn-dimensional manifold, then it has a neighborhood that is diffeomorphic to an nn-dimensional half ball. A half space is defined by a hyperplane in Rn\mathbb{R}^{n}. If xx is a boundary point, then it is possible to find a hyperplane such that most its neighbors lie on the same side of the hyperplane. On the other hand, if xx is an interior point, then any hyperplane will split the neighborhood in half, with roughly half the points on one side and half on the other side.

We assign each point xx a boundary score s(x)∈[0,1]s(x) \in[0,1] that is the percentage of its neighborhood lying on the same side of an “optimal” hyperplane. Boundary points have scores near 11, and manifold points have scores near .5.5. Near a transverse intersection of manifolds, the score is usually higher than .5.5 but lower than 11—for example, near a transverse intersection of two manifolds, the score is near .75.75. (See Figure 6, for example.)1 The algorithm steps are described below.

Boundary scores on noisy intersecting line segments

Figure 6. Boundary scores on noisy intersecting line segments.

The algorithm

  1. Local PCA: For each point xx, we use local PCA to reduce the dimension of its local neighborhood {xi}i=1k\{x_i\}_{i=1}^{k}, where kk is a parameter that controls the size of the neighborhood. If the dimension nn of the manifold is known, then we reduce to nn dimensions; otherwise, we use a spectral gap threshold condition. Let {z⃗i}i=1k\{\vec{z}_i\}_{i=1}^{k} be the neighborhood after dimension reduction and after centering so that xx is mapped to 0⃗\vec{0}.

  1. Hyperplane optimization: We solve for an “optimal” hyperplane that best separates the data points onto a single side of the hyperplane. Every hyperplane is determined by an orthogonal vector w⃗\vec{w} with norm ∥w⃗∥=1\lVert\vec{w}\rVert= 1. A point z⃗i\vec{z}_i lies on the “positive” side of the hyperplane if z⃗i⋅w⃗>0\vec{z}_i \cdot\vec{w} > 0. A hyperplane is good if most of the points lie on the positive side of the hyperplane. To formulate this, we solve the optimization problem

argmax⁡w⃗ f(w⃗)=∑i=1kz⃗i⋅w⃗,subject to g(w⃗)=∥w⃗∥2=1.(1)\underset{\vec{w}}{\operatorname{argmax}}\ f(\vec{w}) = \sum_{i=1}^{k} \vec{z}_i \cdot\vec{w}, \qquad\text{subject to } g(\vec{w}) = \lVert\vec{w}\rVert^{2} = 1. \tag*{(1)}

The function f(w⃗)f(\vec{w}) is proportional to the mean (signed) distance to the hyperplane, and the constraint normalizes the sum so that it cannot be arbitrarily large. By the method of Lagrange multipliers, the solution to our optimization problem is w⃗=∑iz⃗i/∥∑iz⃗i∥\vec{w} = \sum_i \vec{z}_i / \lVert\sum_i \vec{z}_i \rVert.

  1. Boundary score: The boundary score s(x)∈[0,1]s(x) \in[0,1] for point xx is the percentage of neighboring points that lie on the positive side of the hyperplane. Boundary and interior points have scores close to 11 and .5.5, respectively.

As an alternative to our hyperplane optimization step, one could instead aim to maximize the number of points such that z⃗i⋅w⃗≥0\vec{z}_i \cdot\vec{w} \ge0. In contrast, maximizing f(w⃗)f(\vec{w}) encourages but does not force points to lie on the positive hyperplane side. The advantage of our formulation is that it has a fast, closed-form solution. Algorithm 1 runs in about 1s for N=10,000N = 10,000 points in R15\mathbb{R}^{15}.

Algorithm 1 Boundary Detection

Input: Point cloud X\mathcal{X}, neighborhood size kk, PCA spectral gap threshold τ\tau (default τ=7\tau= 7) Output: Boundary score s(x)∈[0,1]s(x) \in[0,1] for each x∈Xx \in\mathcal{X}

  1. for all x∈Xx \in\mathcal{X} do

  2. N←k\mathcal{N} \leftarrow k-nearest neighbors of xx in X\mathcal{X}

  3. {zi}←PCA⁡(N,τ)\{z_i\} \leftarrow\operatorname{PCA}(\mathcal{N},\tau) ▷ Use threshold τ\tau to determine dimension

  4. {zi}←{zi−z}\{z_i\} \leftarrow\{z_i-z\} ▷ Center so projection of xx is at origin

  5. w⃗←∑iz⃗i∥∑iz⃗i∥\vec{w} \leftarrow\dfrac{\sum_i \vec{z}_i}{\left\lVert\sum_i \vec{z}_i\right\rVert} ▷ w⃗\vec{w} is orthogonal to an optimal hyperplane

  6. m←∣{zi∣z⃗i⋅w⃗≥0}∣m \leftarrow\left|\{z_i \mid\vec{z}_i \cdot\vec{w} \ge0\}\right| ▷ Count neighbors on positive side of the hyperplane

  7. s(x)←m/ks(x) \leftarrow m/k ▷ Divide by total size of the neighborhood

  8. end for

  9. return {s(x)}x∈X\{s(x)\}_{x\in\mathcal{X}}

To illustrate the hyperplane optimization step of the algorithm, we sample kk points {z⃗i}\{\vec{z}_i\} from half or full nn-dimensional balls and calculate w⃗\vec{w}. See Figure 1. For each experiment, we define the “accuracy” to be the percentage of points that lie on the positive side of the hyperplane determined by w⃗\vec{w}—this is analogous to the boundary score defined previously. When the points are sampled from a half ball—which models the boundary-point case—the accuracy stays close to 1, even for the smallest neighborhood size that we tested (k=10k = 10). By contrast, when the points are sampled from a full ball—which models the interior-point case—the accuracy is close to 1/21/2. The gap between interior and boundary points persists as the dimension nn increases to n=10n = 10. This is preliminary evidence that the optimized hyperplane reliably distinguishes between boundary and interior points.

Figure 1. Hyperplane optimization on points sampled from half and full balls. Accuracy is the percentage of points that lie on the positive side of the hyperplane orthogonal to w⃗\vec{w}.

Concentration Inequalities for the Boundary Scores

The theorems below can be used to guide a choice of neighborhood size kk given a manifold dimension nn, or to pick a threshold on the boundary scores for identifying boundary points. Our goal is to quantify the distribution of boundary scores s(x)s(x) when xx is either an interior point or a boundary point. To do so, we consider the random variable

References

  1. [1]Osama Al-Dalahmah, Michael G. Argenziano, Adithya Kannan, Aayushi Mahajan, Julia Furnari, Fahad Paryani, Deborah Boyett, Akshay Save, Nelson Humala, Fatima Khan, Juncheng Li, Hong Lu, Yu Sun, John F. Tuddenham, Alexander R. Goldberg, Athanassios Dovas, Matei A. Banu, Tejaswi Sudhakar, Erin Bush, Andrew B. Lassman, Guy M. McKahn, Brian J. A. Gill, Brett Youngerman, Michael B. Sisti, Jeffrey N. Bruce, Peter A. Sims, Vilas Menon, and Peter Canoll. Re-convolving the compositional landscape of primary and recurrent glioblastoma reveals prognostic and targetable tissue states. Nature Communications, 14(1):2586, 2023. doi: 10.1038/s41467-023-38186-1.DOI
  2. [2]Hadar Averbuch-Elor, Nadav Bar, and Daniel Cohen-Or. Border-peeling clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(7):1791–1797, 2020. ISSN 1939-3539.
  3. [3]Aleksandr Berdnikov and Evgeny Liokumovich. Sky sphere representation in language models. arXiv:2607.27092, 2026.arxiv.org/abs/2607.27092
  4. [4]Dylan M. Cable, Evan Murray, Luli S. Zou, Aleksandrina Goeva, Evan Z. Macosko, Fei Chen, and Rafael A. Irizarry. Robust decomposition of cell type mixtures in spatial transcriptomics. Nature Biotechnology, 40(4):517–526, 2022. doi: 10.1038/s41587-021-00830-w.DOI
  5. [5]Xuemei Ding, Yuhua Li, Ammar Belatreche, and Liam P. Maguire. Novelty detection using level set methods. IEEE Transactions on Neural Networks and Learning Systems, 26(3):576–588, 2015. ISSN 2162-2388.DOI
  6. [6]Mingjing Du, Ru Wang, Ru Ji, Xia Wang, and Yongquan Dong. ROBP a robust border-peeling clustering using Cauchy kernel. Information Sciences, 571:375–400, 2021. doi: 10.1016/j.ins.2021.04.089.DOI
  7. [7]Joshua Engels, Eric J. Michaud, Isaac Liao, Wes Gurnee, and Max Tegmark. Not all language model features are one-dimensionally linear. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2405.14860
  8. [8]Walter Gautschi. Some Elementary Inequalities Relating to the Gamma and Incomplete Gamma Function. Journal of Mathematics and Physics, 38(1-4):77–81, 1959. ISSN 0097-1421.DOI
  9. [9]Wes Gurnee and Max Tegmark. Language models represent space and time. In International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2310.02207
  10. [10]Wes Gurnee, Emmanuel Ameisen, Isaac Kauvar, Julius Tarng, Adam Pearce, Chris Olah, and Joshua Batson. When models manipulate manifolds: The geometry of a counting task. arXiv:2601.04480, 2026.arxiv.org/abs/2601.04480
  11. [11]Xiaojie Li, Jiancheng Lv, and Zhang Yi. An Efficient Representation-Based Method for Boundary Point and Outlier Detection. IEEE Transactions on Neural Networks and Learning Systems, 29(1):51–62, 2018. ISSN 2162-2388.
  12. [12]Yuhua Li and Liam Maguire. Selecting Critical Patterns Based on Local Geometrical and Statistical Information. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(6):1189–1201, 2011. ISSN 1939-3539.DOI
  13. [13]Kanti V. Mardia and Peter E. Jupp. Directional Statistics. Wiley Series in Probability and Statistics. Wiley, 1st edition, 1999. ISBN 9780471953339780470316979.DOI

Paper details

vlnc:W_k42wf4j4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI

View statement
Looking for related papers…
Contents