Effective Neural Approximations for Geometric Optimization Problems

Thank you for your comments! We are glad you appreciate the robustness of our framework -- especially with regards to its out-of-distribution performance. We note that the performance of our algorithmic processor module on the $\varepsilon$-kernel task is shows much better performance OOD. Furthermore, using this $\varepsilon$-kernel processor in the encoder-decoder-processor on more complex geometric optimization problem allows for accurate approximations even with only re-training the encoder/decoder.

Regarding Q1, about the fatness of the point set: First, we note that $\alpha$-fatness is a standard assumption in computational geometry. Intuitively, a larger $\alpha$ indicates that the point cloud is not excessively “skinny,” while smaller values of $\alpha$ correspond to increasingly elongated or degenerate point sets. In the extreme case, $\alpha$ can shrink inversely with the number of points in the input—this occurs when the point cloud is effectively degenerate, exhibiting no variation in at least one direction. Our theoretical guarantees hold even for point sets with low $\alpha$ values; the approximation factor in our analysis scales with $\alpha$. Consequently, as $\alpha$ decreases (i.e., the point sets become “skinnier”), the theoretical approximation factor worsens, and more parameters are required. Despite this, we observe strong empirical performance across a wide range of $\alpha$ values (cf. Figure 6 in the appendix). Additionally we find that real-world datasets tend to have relatively large $\alpha$ values. For example, in the widely used ModelNet dataset, where each point cloud lies within the bounding box $[-1, 1]^d$, the average $\alpha$-fatness is 0.81 (with the maximum possible value being 1).

Regarding Q2, baselines: Thank you for your suggestion regarding comparing to more neural and algorithmic baselines. We will reiterate our response to Reviewer VDgZ. To the best of our knowledge, ours is the first work considering using neural networks as solvers for geometric extent measure problems. Therefore, to understand the power of leveraging algorithmic frameworks in our $\varepsilon$-kernel approximating NN, we compare with natural neural baselines. In our paper, we propose baselines built on the well-known encoder-processor-decoder paradigm (see [1]). We use a simple embedding MLP as the encoder network, the processor network is some suitable architecture (e.g. a transformer or sumformer) which processes embedded point cloud as input and aggregates the resulting representations into a global feature vector, and the a final MLP as the decoder network. The Sumformer and transformer versions of this baseline, $\mathcal{S}\_{\mathrm{Baseline}}$ and $\mathcal{T}\_\mathrm{Baseline}$ respectively, are exactly the neural baselines used for comparison in our paper.

To give a case study as to why this is the neural baseline we compare against, we consider the minimum enclosing ball problem. The most straightforward neural approach would be to directly aggregate the point cloud input into a global feature vector using some architecture (sumformer or transformer) and then directly compute a final estimate for the radius of the minimum enclosing ball with a final MLP. We will refer to the Sumformer versions of this baseline as $\mathcal{S}_\mathrm{Direct}$. Our included encode-process-decode baseline is a slightly more complicated version of this as we do an initial encoding step with the encoder network. We show in Tables 2 and 13 in our paper that our encode-process-decode extent measure model using the $\varepsilon$-kernel-approximating Sumformer network as the processor network outperforms both encode-process-decode baselines ($\mathcal{S}\_\mathrm{Baseline}$ and $\mathcal{T}\_\mathrm{Baseline}$) on the minimum enclosing ball problem. To further illustrate the utility of our algorithmically aligned extent measure model $\mathcal{S}\_\mathrm{extent}$, we include additional results comparing our original baseline $\mathcal{S}\_\mathrm{Baseline}$ against $\mathcal{S}\_\mathrm{Direct}$ on the minimum enclosing ball problem for the SQUID dataset in the table below (Table A).

Additionally, we thank the reviewer for the suggestion of comparing against additional baselines. In Table B below, we provide a further comparison of our extent measure approximating model, $\mathcal{S}\_\mathrm{extent}$, against the classical algorithms for the minimum enclosing ball task with different input point cloud sizes. In particular, we compare our neural model's runtime at inference time with Welzl's algorithm. Since Welzl's algorithm is an exact algorithm, we include a comparison to the classical exact $\varepsilon$-kernel algorithm followed by Welzl's algorithm. While our network is less accurate than using a $\varepsilon$-kernel followed by Welzl's algorithm, we observe that our network is significantly faster than all baseline algorithms and more accurate than neural baselines.

Table B. Comparison of extent measure model against algorithmic baselines

Additionally, we provide a comparison of our $\varepsilon$-kernel-approximating network, $\mathcal{S}\_\varepsilon$, against the additional direct neural baseline described above as well as the algorithmic $\varepsilon$-kernel baselines for input point clouds of varying sizes in $\mathbb{R}^5$. Note that some comparison already exists in our paper as we compare $\mathcal{S}\_\varepsilon$ against the relaxed-$\varepsilon$-kernel computed in Algorithm 1 (cf. Appendix D, Figures 5-8).

Table C. Comparison of $\mathcal{S}\_\varepsilon$ against baselines

We will include more comparisons with both classical algorithmic and neural baselines for extent measure problems in our final manuscript.

[1] "Relational Inductive Biases, Deep Learning, and Graph Networks" (Battaglia, et al. 2018)

Regarding Q4, applicability to real-world datasets: First, we note that the SQUID dataset contains boundary contours of approximately 1100 marine animals. We use this dataset because boundaries are a natural setting for $\varepsilon$‑kernels and it provides a real‑world 2D point cloud benchmark. Additionally, we see that both the relaxed-$\varepsilon$-kernel and the encode-process-decode extent measure model are effective given the real-world 3D point clouds in ModelNet.

Thanks for providing these baselines. So you gain around ~8x-10x speed-ups compared to (ε-kernel + Welzl's algorithm) but the error increases by ~100x?

This should be in your paper as a major point of discussion / limitation

Thank you for the observation. We will acknowledge the limitation you point out. However, we would like to clarify that the main contribution of our work is proposing a general framework for solving extent-measures problems, especially those for which an efficient approximation algorithm does not exist. We use minimum enclosing ball as an example of a faithful extent measure problem which can be efficiently solved with our architecture. Because minimum enclosing ball is an LP type problem, it has a relatively efficient solution (although our neural method is still faster). However, we emphasize that our architectures can also work effectively for non LP-type problems where there are no efficient solutions. In fact, we have done additional experiments comparing our architecture with the baseline $\varepsilon$-kernel followed by exact algorithm for minimum-width spherical shell (annulus), which is a non LP-type problem. Here, we find a speedup of approximately 305x with N=200, while still reporting a relatively low error. Note that we include the percentage of points excluded in addition to the error in the computed widths and that our method outperforms the baseline in terms of proportion of points excluded from the approximated spherical shell.

Furthermore, we emphasize that our theoretical results show that our neural architectures can approximate extent measure problems without requiring parameters scaling with input size as compared to previous point cloud processing architectures, which required the parameters to scale at least linearly with the size of the input point cloud.

Thank you for your time and careful review. In what follows, we will address your main questions. We think that there might be some misunderstanding of our paper. In particular, as we will detail below, our paper does have a related work section and we also have several baselines methods for comparison.

Regarding Q1, motivation: We would like to clarify our motivation here. As we explain in the introduction of our paper, the key motivation behind our work is to design efficient and practical neural models to solve hard problems in a data-driven manner. In particular, we consider problems which take point cloud data as input. We are interested in models that both have the expressivity to approximately solve the problem using bounded size (i.e. fixed number of parameters) and produce high quality and efficient approximations.

First, we observe that popular models for handling sets or sequences such as DeepSets, Sumformers, and Transformers usually require model complexity scaling with the size of input point sets in order to $\varepsilon$-approximate an arbitrary function. Our work shows that by aligning neural design with algorithmic principles, specifically by leveraging the frameworks of $\varepsilon$-kernels and linearization, we can construct two neural architectures which solve geometric extent measure problems with model complexity independent of the input point set size. We note that finding accurate and efficient approximation algorithms for extent measure problems in the case of large point clouds remains of interest to the computational geometry community (see [1]).

Importantly, our paper goes beyond just an expressivity argument. We demonstrate through extensive empirical experiments that our models are more efficient and accurate than both natural neural baselines and pure algorithmic approaches in terms of both approximating $\varepsilon$-kernels as well as solving extent measure problems. While our neural models are inspired by algorithmic approaches, those algorithmic ideas only provide high level scaffolding: we demonstrate through extensive empirical experiments that their data-driven design makes them more efficient and accurate than both natural neural baselines (see Tables 2, 13, 14, and 15 in our paper) and pure algorithmic approaches (see Figures 5-8 in our paper). Below, we also include new experiments comparing the runtime of our neural models at inference time with classical algorithms and new natural baselines (Tables A and B below).

In short, we believe that our work provides a compelling example that using algorithmic ideas can lead to more practical neural models (than both classical algorithmic approaches and baseline neural networks) for solving a family of geometric optimization problems, and contribute to the general research direction of neural algorithmic design. We will be happy to revise our Introduction to make these points more clear.

[1] "Computing Instance-Optimal Kernels in Two Dimensions" (Agarwal and Har Peled, Discrete and Computational Geometry 2024)

Regarding Q2, our related work section: In fact, we do have a related work section on page 2. We reiterate the main points in our related work section here. First, there are many architectures focused on point cloud processing -- the oldest of which are DeepSets and PointNet and more recently, transformers. Most, if not all, applications to date have come from computer vision. The utility of neural networks to act as solvers for computational geometry is previously unexplored. Our work is the first to apply neural networks for approximating solutions to common geometric problems from computational geometry. Therefore, in lieu of comparisons to previous work, we propose our own neural baselines for comparison in the paper (which we will further elaborate on in our response to your question about baselines). In our related works section, we acknowledge several previous works on studying the expressivity of point cloud networks. In particular, we highlight that for general functions over point clouds, the best known lower bounds for expressivity still depends linearly on the size of the input point set (See [1]). We emphasize that for the specific case of extent measure problems, our work demonstrates that one can achieve $\epsilon$-accuracy with parameters independent of the input point set size using our specific sumformer architecture.

[1]"Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem" (Amir, et al. NeurIPS 2023)

Regarding Q3, baselines: Thank you for your suggestion regarding comparing to more neural and algorithmic baselines. To the best of our knowledge, ours is the first work considering using neural networks as solvers for geometric extent measure problems. Therefore, to understand the power of leveraging algorithmic frameworks in our $\varepsilon$-kernel approximating NN, we compare with natural neural baselines. In our paper, we propose baselines built on the well-known encoder-processor-decoder paradigm (see [1]). We use a simple embedding MLP as the encoder network, the processor network is some suitable architecture (e.g. a transformer or sumformer) which processes embedded point cloud as input and aggregates the resulting representations into a global feature vector, and the a final MLP as the decoder network. The Sumformer and transformer versions of this baseline, $\mathcal{S}\_{\mathrm{Baseline}}$ and $\mathcal{T}\_\mathrm{Baseline}$ respectively, are exactly the neural baselines used for comparison in our paper.

To give a case study as to why this is the neural baseline we compare against, we consider the minimum enclosing ball problem. The most straightforward neural approach would be to directly aggregate the point cloud input into a global feature vector using some architecture (sumformer or transformer) and then directly compute a final estimate for the radius of the minimum enclosing ball with a final MLP. We will refer to the Sumformer versions of this baseline as $\mathcal{S}_\mathrm{Direct}$. Our included encode-process-decode baseline is a slightly more complicated version of this as we do an initial encoding step with the encoder network. We show in Tables 2 and 13 in our paper that our encode-process-decode extent measure model using the $\varepsilon$-kernel-approximating Sumformer network as the processor network outperforms both encode-process-decode baselines ($\mathcal{S}\_\mathrm{Baseline}$ and $\mathcal{T}\_\mathrm{Baseline}$) on the minimum enclosing ball problem. To further illustrate the utility of our algorithmically aligned extent measure model $\mathcal{S}\_\mathrm{extent}$, we include additional results comparing our original baseline $\mathcal{S}\_\mathrm{Baseline}$ against $\mathcal{S}\_\mathrm{Direct}$ on the minimum enclosing ball problem for the SQUID dataset in the table below (Table A).

Additionally, we thank the reviewer for the suggestion of comparing against additional baselines. In Table B below, we provide a further comparison of our extent measure approximating model, $\mathcal{S}\_\mathrm{extent}$, against the classical algorithms for the minimum enclosing ball task with different input point cloud sizes. In particular, we compare our neural model's runtime at inference time with Welzl's algorithm. Since Welzl's algorithm is an exact algorithm so we include a comparison to the classical exact $\varepsilon$-kernel algorithm followed by Welzl's algorithm. While our network is less accurate than using a $\varepsilon$-kernel followed by Welzl's algorithm, we observe that our network is significantly faster than all baseline algorithms and more accurate than neural baselines.

Table B. Comparison of extent measure model against algorithmic baselines

Additionally, we provide a comparison of our $\varepsilon$-kernel-approximating network, $\mathcal{S}\_\varepsilon$, against the additional direct neural baseline described above as well as the algorithmic $\varepsilon$-kernel baselines for input point clouds of varying sizes in $\mathbb{R}^5$. Note that some comparison already exists in our paper as we compare $\mathcal{S}\_\varepsilon$ against the relaxed-$\varepsilon$-kernel computed in Algorithm 1 (cf. Appendix D, Figures 5-8).

Table C. Comparison of $\mathcal{S}\_\varepsilon$ against baselines

We will include more comparisons with both classical algorithmic and neural baselines for extent measure problems in our final manuscript.

[1] "Relational Inductive Biases, Deep Learning, and Graph Networks" (Battaglia, et al. 2018)

Regarding Q4, visualizations: Thank you for your suggestion, we will include many more visualizations in our final manuscript. We would like to note that there are further experiments and visualizations present in our Appendix D.

After reading the authors' rebuttal, I find that the following concerns remain unaddressed:

• Unclear Motivation: The motivation for using neural networks to solve the geometric "extent measure" problem remains unclear. One possible advantage should be faster inference; however, the authors have not provided sufficient comparisons with existing methods to demonstrate this. In fact, the results in the provided table (Table B in the rebuttal) suggest that the original exact algorithm is already fast enough to support real applications. More importantly, the authors should compare the proposed method with widely-used approximate algorithms, but this important comparison is currently missing.

• Insufficient Comparisons: Providing comparisons with traditional methods is an important aspect of the experimental evaluation. Instead of comparing only with self-implemented neural variants, the authors should have included comparisons with traditional methods. Initially, no such comparisons were provided. During the rebuttal, the authors only included comparisons with one baseline on a single task, which is insufficient.

• Very Limited "Related Work" in Paper: Although the authors included a "related work" paragraph, they did not provide a discussion about the differences between the proposed algorithm and traditional algorithms.

In my opinion, the current version is not ready for publication. I will maintain my original score.

I appreciate the effort made by the authors to provide additional results. However, I would like to emphasize that my major concern remains unresolved: the original main paper omits several critical components, including necessary discussions (e.g., detailed reviews of traditional methods) and sufficient comparisons with existing state-of-the-art traditional methods.

Additionally, the experimental results provided during the rebuttal involve only one traditional baseline on a single task, without a detailed description of the experimental setup. Furthermore, Figures 5–8 in the original paper are included in the supplementary material, but they seem to be based on self-implemented baselines, as no references are provided.

As a result, I believe the current draft is not yet ready. The motivation and contribution remain unclear, and the effectiveness is inadequately demonstrated.

Thank you for time and careful review. We are glad the reviewer appreciates both our theoretical results relating the $\varepsilon$-kernel framework to neural networks as well as the extensive practical evaluation for both approximating $\varepsilon$-kernels as well as three different extent measure problems. Thank you for your suggestion regarding visual aids, we will definitely add more to our final manuscript.

Regarding Q1 about softmax vs. $L_1$ normalization: We thank the reviewer for raising this question, which is a very valid one. In fact, it turns out that using softmax can serve just as well as $L_1$ normalization for our theoretical framework. The key requirement for our results to hold is simply a mechanism to transform the vector $\rho_\varepsilon(\mathbf{a})$ (which intuitively records how far each point is from the maximum point in a given direction) into a valid probability distribution over the input point set, assigning zero weight to any points located more than $\varepsilon w(A)$ from the maximum. While we adopt $L_1$ normalization, one could equivalently use a softmax variant e.g. $\frac{e^{z_i} - 1}{\sum_j \left(e^{z_j} - 1\right)}.$ Any normalization scheme satisfying the aforementioned requirement will work as we only need the normalization in order give final output points which are convex combinations of the input points lying within $\varepsilon w(A)$ of the true maximum in a given direction. We will add this softmax guarantee to our revised manuscript. Note that in Appendix A.5, Table 5, we compare softmax against $L_1$-normalization and find that softmax works much better in practice.

Regarding Q2, about example extent measure problems: Thank you for your suggestions. A linearizable unfaithful extent measure that one can keep mind while reading Section 4 is the minimum enclosing annulus. In fact, the appendix has an example of using relaxed-$\varepsilon$-kernels with the minimum enclosing annulus problem.

Regarding Q3, input point set size: Yes, our network is easily able to handle input point sets of different sizes as point sets of any size can be used as inputs to sumformers. Additionally, our theoretical results provide a guarantee that the network can still $\varepsilon$-approximate solutions to extent measure problems without scaling the number of parameters in the network.

Regarding Q4, about hyperparameter searching: For our hyperparameter search on the $\varepsilon$-kernel task, we chose the sumformer/transformer and MLP depth from $\{2, 3, 4\}$, the hidden dimension from $\{128, 256, 512, 1024\}$, and embedding dimension from $\{16, 32\}$. For the extent-measures models, we fix the hyperparameters of the processor based on the best configuration from the $\varepsilon$-kernel task and vary those of the encoder and decoder, randomly selecting combinations and manually adjusting promising configurations. The depth of both the encoder and decoder MLPs are sampled from $\{2, 3, 4\}$, and the width from $\{64, 128, 256\}$.

Regarding Q5, robustness to input noise: We believe that our models are robust to unseen noisy data as they generalize well to out-of-distribution data at inference time. In Table 9 and 10, we have detailed results showing the performance of our relaxed-$\varepsilon$-kernel approximating network trained on simple synthetic datasets but tested of a variety of synthetic and real datasets. In these tables, we observe that the relaxed-$\varepsilon$-kernel approximating network, which is aligned with Algorithm 1 in our manuscript, displays similar test error across all datasets (including those which are out-of-distribution). Additionally, we show in Table A (in our response to Reviewer VDgZ) for our extent measure approximating network, a model trained on point clouds sampled from uniform disk still performs well on real-world SQUID dataset.

Thank you for your time and careful review! We are glad the reviewer appreciates our introduction of the relaxed-$\varepsilon$-kernel.

Regarding algorithmic alignment: Before we respond to your questions, we would first like to elaborate on the motivation and benefit of algorithmic alignment. Overall, the framework of algorithmic alignment allows us to use algorithmic structure as a scaffold for the design of some task-specific network. By designing the model to imitate some algorithmic flow, we bias the model towards learning some task-specific subroutine which will help it generalize better to out-of-distribution data. Notably, the data-driven model may learn something different and better than the original algorithm used to design the model. See [1], [2], [3] for previous examples of how algorithmic alignment enhances model performance.

In our work, we use two types of algorithmic alignment. First, we observe the alignment between the $\varepsilon$-kernel algorithm and the SumFormer to define a relaxed-$\varepsilon$-kernel approximating neural network. Second, we use the relaxed-$\varepsilon$-kernel approximating neural network as a processor in the encode-process-decode (EPD) framework. This entire encode-process-decode framework can be aligned with solving a geometric extent measure problem via linearization (encode), generating a coreset for the problem with a $\varepsilon$-kernel (process), and finally solving the extent measure problem with a downstream algorithm (decode). Theoretically, this alignment allows us to show that geometric extent measure problems can be solved with neural networks with model complexity independent of the size of the input point set.

Similar to previous work on algorithmic alignment, we empirically observe our aligned sumformer model, denoted as $\mathcal{S}\_\varepsilon$, exhibits better performance in approximating $\varepsilon$-kernels as compared to a baseline transformer architecture (cf. Table 1) and our aligned EPD model is more accurate than natural neural baselines in approximating solutions to extent measure tasks (cf. Table 2). In fact, when compared to Algorithm 1 which guides the design of our model, we see that $\mathcal{S}\_\varepsilon$ outperforms the relaxed-$\varepsilon$-kernel algorithm in terms of accuracy (cf. Figures 5-8 in the Appendix). Below, we include additional comparisons for $\mathcal{S}\_\varepsilon$ against both the relaxed-$\varepsilon$-kernel and the classical $\varepsilon$-kernel algorithm in $\mathbb{R}^5$ at different input point set sizes. We see that $\mathcal{S}_\varepsilon$ has a much lower runtime and error, where error is measured by the directional width error, than both algorithmic baselines.

Additionally, for the EPD framework, we see more evidence of algorithmic alignment improving the performance of the model in Table 2: the extent measure networks with frozen processor modules which were explicitly trained on approximating $\varepsilon$-kernels outperform the end-to-end trained model.

Finally, we appreciate your observation regarding the behavior of the test error on out-of-distribution datasets in Figures 9 and 10. However, we would like to clarify that these figures are intended to support our decision to train the models for only 200 epochs where performance on out-of-distribution data is strong. The degradation in out-of-distribution performance over longer training durations is consistent with this interpretation and does not contradict our core claims. In sum, algorithmic alignment provides high-level guidance for designing networks which can (1) generalize well on the specific algorithmic task which it is aligned to and (2) provide boosts in performance for downstream tasks in which the network can be used as a module.

[1] The CLRS Algorithmic Reasoning Benchmark (Veličković et al., ICML 2022).
[2] Neural Execution of Graph Algorithms (Veličković et al. ICLR 2020).
[3] Learning Graph Algorithms with Recurrent Graph Neural Networks (Grötschla et al. GCLR Workshop @ AAAI 2023).

Regarding Q1 and Q5, about the complexity of Algorithm 1 and scaling with dimension $d$: Yes, the complexity of Algorithm 1 is bounded in the number of input points but scales exponentially with the dimension $d$. The alignment with Algorithm 1 makes it so that our model has bounded model complexity in terms of the size of the input point cloud.
Scaling with the size of the input point set is the far more pernicious scaling for most real-world point cloud processing applications as for most applications use low-dimensional but large scale point clouds (potentially millions of points per input point set). Therefore, scaling with the dimension is fine (as most applications use low dimensions) but the required model parameters scaling with the number of points in order to keep some level of expressivity is less ideal. Our universality guarantee which avoids dependence on the size of the input point cloud is particularly significant, as prior universality results for standard point cloud models required the number of parameters to scale with the size of the input point set in order to achieve universality.

Regarding Q2, about the fatness of the point set: First, we note that $\alpha$-fatness is a standard assumption in computational geometry. Intuitively, a larger $\alpha$ indicates that the point cloud is not excessively “skinny,” while smaller values of $\alpha$ correspond to increasingly elongated or degenerate point sets. In the extreme case, $\alpha$ can shrink inversely with the number of points in the input—this occurs when the point cloud is effectively degenerate, exhibiting no variation in at least one direction. Our theoretical guarantees hold even for point sets with low $\alpha$ values; the approximation factor in our analysis scales with $\alpha$. Consequently, as $\alpha$ decreases (i.e., the point sets become “skinnier”), the theoretical approximation factor worsens, and more parameters are required. Despite this, we observe strong empirical performance across a wide range of $\alpha$ values (cf. Figure 6 in the appendix). Additionally we find that real-world datasets tend to have relatively large $\alpha$ values. For example, in the widely used ModelNet dataset, where each point cloud lies within the bounding box $[-1, 1]^d$, the average $\alpha$-fatness is 0.81 (with the maximum possible value being 1).

Regarding Q3, about the “alignment” of the model with an algorithm: We touched on this point previously but will reiterate it in brief again. The alignment to Algorithm 1 as a high-level scaffold for our models. However, the data-driven model may learn something different and better than the original algorithm. Therefore, we are unable to directly observe if the learned weights implement Algorithm 1. We do observe that our aligned sumformer model learns to approximate the relaxed-$\varepsilon$-kernel better than a baseline transformer architecture (cf. Table 1) and to our point that the data-driven model learns a more efficient and accurate algorithm than the original, we observe in Figures 5–8 in our appendix that our trained models outperform the baseline algorithm in terms of error. In our revised manuscript, we will include more results comparing the runtime and accuracy of our model against the baseline algorithm as well as another natural baseline neural architecture. Preliminary results of this nature are included in our response to Reviewer VDgZ in Table C. For example, we find that for a point cloud in $\mathbb{R}^5$ with 2000 points, our relaxed-$\varepsilon$-kernel approximating neural network computes an output $\varepsilon$-kernel with 150 points in 0.0003 seconds while Algorithm 1 requires 0.002 seconds to output a $\varepsilon$-kernel with 150 points.

Regarding experiments on higher-dimensional point clouds: We conducted additional experiments on synthetic point clouds in 10 dimensions and summarize some preliminary results. For a point cloud with 2000 points sampled uniformly from a randomly stretched and shifted ellipse, our SumFormer model (outputting a $\varepsilon$-kernel with 200 points) has a directional width error of 0.252 while the output point cloud from Algorithm 1 (also outputting a $\varepsilon$-kernel with 200 points) has a directional error of 0.269. Additionally, our SumFormer model has runtime $2 \times 10^4$ seconds while Algorithm 1 has runtime $3.3 \times 10^3$ seconds. In short, even for high-dimensional datasets, the directional width error for our model is better than the baseline algorithm while being significantly more efficient. We will include more results on high-dimensional data in our revision.