Boundary Detection for High-Dimensional Point Clouds

Abigail Hickok; Valerio Galanti; Osama Al Dalahmah; Andrew J. Blumberg

cs.LGOct 16, 2026

Boundary Detection for High-Dimensional Point Clouds

Authors: Abigail Hickok, Valerio Galanti, Osama Al Dalahmah, Andrew J. Blumberg

Organizations: Department of Mathematics Columbia University New York, NY, USA · Department of Computer Science Columbia University New York, NY, USA · Department of Pathology and Cell Biology Columbia University New York, NY, USA · Department of Mathematics, Department of Computer Science, Irving Institute for Cancer Dynamics Columbia University New York, NY, USA

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.

Figures & tables

Panel of Figure 1 — 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 $\vec{w}$ .

Figure 2: The vectors $\vec{v_{j}}$ for points $\{x_{ij}\}$ (orange) in a local neighborhood of a point $x_{i}$ (red) within a larger point cloud that is sampled from (left) a thin strip in $\mathbb{R}^{2}$ with noise and (right) a half plane.

DU (us)	Hyperplane (us)	LoDD	BEPS	RU	CO	BORDER	BP (Gauss.)	BP (Cauchy)
1.000	1.000	1.000	1.000	0.474	0.447	0.474	0.425	0.436

Table 1: Boundary (

\mathinner{\!\left\lVert x\right\rVert}>.98

) vs deep-interior (

\mathinner{\!\left\lVert x\right\rVert}<.23

) AUC for

N=10,000

points sampled non-uniformly from a 2D disk. In the interior, there is a “well” (

r<.23

) where the density is

1/9

that of the density in the outer region (

r>.67

). The density increases linearly in between.

Figure 3: Boundary scores ( $k=100$ ) for two synthetic data sets ( $N=10^{4}$ ) with low noise levels.

Figure 4: Boundary scores ( $N=10,000$ , $k=100$ ) on the Henneberg minimal surface embedded in $\mathbb{R}^{15}$ with isotropic Gaussian noise ( $\sigma=.02$ ), plotted in $\mathbb{R}^{3}$ .

Figure 5: Analysis of boundary scores on disks embedded in $\mathbb{R}^{D}$ with Gaussian noise $\sigma=.01$ (size $N=10,000$ points, with $k=100$ ).

Figure 6: Boundary scores on noisy intersecting line segments.

Figure 7: Boundary scores at high noise, for 2D disks ( $N=10,000$ ) embedded in $\mathbb{R}^{D}$ with Gaussian noise $\sigma$ . We use neighborhood size $k=100$ . Boundary and interior points are defined as points with norm $>.95$ and $<.8$ , respectively, with norm computed in the $xy$ plane.

Figure 8: For points $x$ near the boundary of a 2D disk or $n$ -ball ( $\mathinner{\!\left\lVert x\right\rVert}>.95$ ), we compare the estimated boundary normal with the ground-truth normal $-x/\mathinner{\!\left\lVert x\right\rVert}$ . We plot median error and IQR.

Panel of Figure 10 — Figure 10: Boundary detection on the character-counting manifold for Pythia-2.8B.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 11 — Figure 11: We calculate the vector $\vec{w}$ that is the solution to Equation 1 in our hyperplane method, where the accuracy of $\vec{w}$ is the percentage of points $\{z_{i}\}$ such that $\vec{w}\cdot\vec{z}_{i}\geq 0$ . (A) 2D half ball with normal $(1,0)$ and $k=50$ points, with accuracy $.98$ , (B) 2D full ball with $k=50$ and accuracy $.5$ , (C) 3D half ball with normal $(0,0,1)$ and $k=100$ , with accuracy $.99$ , and (D) 3D full ball with $k=100$ and accuracy $.6$ .

Figure 12: We sample $N=10,000$ points non-uniformly from a 2D disk. In the interior, there is a “well” ( $r<.23$ ) where the density is $1/9$ that of the density in the outer region ( $r>.67$ ). The density increases linearly in between. For each method, we calculate the AUC value for boundary points ( $\mathinner{\!\left\lVert x\right\rVert}>.98$ ) vs. interior well points ( $\mathinner{\!\left\lVert x\right\rVert}<.23$ ), using neighborhood size $k=100$ . In the top row, we show the methods that are able to handle non-uniform density. In the bottom row, we show the methods that confuse boundary points and low-density interior points.

Figure 13: Boundary scores for four synthetic data sets with low noise levels. Each point cloud has $N=10,000$ points, and we use neighborhood size $k=100$ .

Figure 14: Boundary scores for three synthetic data sets embedded in $\mathbb{R}^{15}$ with noise. Scores here are plotted in $\mathbb{R}^{3}$ .

Figure 15: Boundary scores on disks embedded in $\mathbb{R}^{15}$ with Gaussian noise $\sigma=.01$ , with $N=10,000$ points. We use neighborhood size $k=100$ . We plot only the first two coordinates.

Figure 16: Boundary scores for 2D disks embedded in $\mathbb{R}^{3}$ with isotropic Gaussian noise $\sigma=.05$ , projected here to $\mathbb{R}^{2}$ .

Figure 17: Boundary scores on a point cloud with $N=10,000$ points sampled from a $10$ -dimensional ball in $\mathbb{R}^{10}$ , with isotropic Gaussian noise ( $\sigma=.01$ ). The ground-truth boundary is difficult to display in $2$ D because it is $9$ -dimensional, so instead we take a thin 2D slice (a slightly thickened disk) the ball, plotting the $1500$ points closest to the $xy$ plane. Because of the curvature of the boundary (a sphere), the boundary appears thicker than the 2D balls in earlier figures, but this is an artifact of the way we are taking a slice and projecting to $\mathbb{R}^{2}$ .

Figure 18: HP and DU boundary scores on the ST1A1 glioblastoma slice at neighborhood sizes $k=75,100,150$ .

Panel of Figure 19 — Figure 19: Boundary detection on the character-counting manifold for Llama-3.1-8B. In (c), we calculate normal vectors only for the top 10% scoring boundary points.

Figure 20: Point clouds are sampled from 2D disks embedded in $\mathbb{R}^{D}$ for $D=3,5,8,10,12,15$ with Gaussian noise level $\sigma=.01$ . Each point cloud has $N=10,000$ points, and we use neighborhood size $k=100$ . Interior points are defined to be points with norm less than $.8$ , and boundary points are defined to be points with norm larger than $\tau_{B}$ , which increases from $\tau_{B}=.91$ to $\tau_{B}=.98$ across the panels. In each panel, we plot the AUC values as a function of ambient dimension $D$ for each of the three methods.

Figure 21: At each noise level $\sigma$ , we sample a point cloud from a 2D disk in $\mathbb{R}^{3}$ with isotropic Gaussian noise. Each point cloud has $N=10,000$ points, and we use neighborhood size $k=100$ . Interior points are defined to be points with norm less than $.8$ , and boundary points are defined to be points with norm larger than $\tau_{B}$ , which increases from $\tau_{B}=.91$ to $\tau_{B}=.98$ across the panels. In each panel, we plot the AUC values as a function of noise level $\sigma$ for each of the three methods.

Figure 22: At each ambient dimension $D$ , we sample a point cloud from a 2D disk in $\mathbb{R}^{D}$ with isotropic Gaussian noise $\sigma=.05$ . Each point cloud has $N=10,000$ points, and we use neighborhood size $k=100$ . Interior points are defined to be points with norm less than $.8$ , and boundary points are defined to be points with norm larger than $\tau_{B}$ , which increases from $\tau_{B}=.91$ to $\tau_{B}=.98$ across the panels. In each panel, we plot the AUC values as a function of ambient dimension $D$ for each of the four methods.

	Pythia-2.8B	Llama-3.1-8B
Total tokens	271,100	269,651
Non-newline tokens	250,437	250,641

Appendix

Table 2: Number of tokens extracted for each model.

Variant	Vector	Score
CO ( Wang et al., 2018 )	$\vec{v_{i}}$	$k^{2}\sum_{j=1}^{k}m_{i}^{-1}m_{j}^{-1}\vec{v_{i}}\cdot\vec{v_{j}}$
Directional uniformity	$\vec{v_{i}}$	$\sum_{j=1}^{k}\vec{v_{i}}\cdot\vec{v_{j}}$
CO magnitude	$\vec{v_{i}}$	$\mathinner{\!\left\lVert\vec{v_{i}}\right\rVert}$
Cosine	$\vec{v_{i}}$	$\cos(\vec{v_{i}},\sum_{j}\vec{v_{j}})$
Sum displacement	$\vec{u_{i}}$	$\sum_{j}\vec{u_{i}}\cdot\vec{u_{j}}$
Mean direction	$\vec{u_{i}}$	$\sum_{j}\cos(\vec{u_{i}},\vec{u_{j}})$

Appendix

Table 3: Other boundary-detection methods that we tested.

Panel of Figure 23 — Figure 23: We compare the variants from Table 3 . (A) Scores on the non-uniformly sampled disk from Figure 12 with $N=10,000$ points and neighborhood size $k=100$ . AUROC scores are for boundary points (norm $>.98$ ) vs deep interior points (norm $<.23$ ), like in Figure 12 . AUROC scores for boundary vs. interior points on 2D disks and $n$ -balls, where interior and boundary points are defined as having norms $<.8$ and $>.95$ , respectively.

Point Cloud Understanding

Point cloud understanding turns sparse 3D measurements into object, scene, shape, and motion information for machines.

See all 44 papers

A Mean Curvature Approach to Boundary Detection: Geometric Insights for Unsupervised Learning
May 5, 2026Alexandre L. M. LevadaGeometric Representation Learning
Federal University of São Carlos 13565-905, São Carlos-SP, Brazil
Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds
Oct 19, 2026Snir Hordan, Harm Derksen, Mircea Petrache +1Point Cloud Learning Equivariant Neural Networks
Technion – Israel Institute of Technology · Northeastern University · Pontificia Universidad Católica de Chile
Heat Field Signatures: From Point Clouds to Smooth Geometry
Sep 7, 2026Yuanqing Wang, Yapeng Tian, Baris CoskunuzerPoint Cloud Learning Geometric Representation Learning
Dept. of Math. Sciences University of Texas at Dallas Richardson, TX, USA · Dept. of Computer Science University of Texas at Dallas Richardson, TX, USA

May 5, 2026J/K move · Enter open · S save

A Mean Curvature Approach to Boundary Detection: Geometric Insights for Unsupervised Learning

Alexandre L. M. Levada

Federal University of São Carlos 13565-905, São Carlos-SP, Brazil

Geometric Representation Learning

Open paper AskPDF arXiv

Accurate boundary detection in high-dimensional data remains a central challenge in unsupervised learning, particularly in the presence of non-linear structures and heterogeneous densities. In this work, we introduce Mean Curvature Boundary Points (MCBP), a novel geometric framework grounded in Geometric Machine Learning that departs from traditional density-based approaches by explicitly modeling the intrinsic curvature of the data manifold. The method relies on a discrete approximation of the shape operator, estimated from local k-nearest neighbor patches, to compute pointwise mean curvature without requiring explicit manifold parametrization. The key insight of MCBP is to use mean curvature as a principled descriptor of boundary structure: high-curvature regions naturally correspond to transitions between clusters, geometric irregularities, and low-density interfaces. This yields a unified geometric interpretation of boundary, outlier, and transition points. We further introduce an adaptive percentile-based thresholding scheme that enables multiscale boundary extraction without relying on ad hoc density parameters. Beyond detection, we propose a curvature-driven data decomposition that separates samples into smooth (low-curvature) and boundary (high-curvature) subsets, effectively acting as a non-linear geometric filtering mechanism. This representation enhances cluster separability and improves the robustness of downstream unsupervised algorithms. Extensive experiments on synthetic and real-world datasets demonstrate that MCBP consistently improves clustering performance, particularly in complex and high-dimensional scenarios. These results position MCBP as a concrete contribution to Geometric Machine Learning, highlighting the potential of curvature-aware analysis as a unifying paradigm bridging differential geometry and data-driven modeling.

Abstract

Point Cloud Understanding

Explore similar work

A Mean Curvature Approach to Boundary Detection: Geometric Insights for Unsupervised Learning

Degree Bounds for Separating Polynomial and Neural Invariants for Point Clouds

Heat Field Signatures: From Point Clouds to Smooth Geometry