Effective Neural Approximations for Geometric Optimization Problems
Authors: Samantha Chen
Oren Ciolli
Anastasios Sidiropoulos
Yusu Wang
Venue: NeurIPS 2025 poster ()
Keywords: geometric deep learning
computational geometry
neural networks
point clouds
Primary area: deep_learning
TL;DR: We introduce neural approximation frameworks for approximating a family of geometric shape-fitting problems.

Abstract: Neural networks offer a promising data-driven approach to tackle computationally challenging optimization problems. 
In this work, we introduce neural approximation frameworks for a family of geometric "extent measure" problems, including shape-fitting descriptors (e.g. minimum enclosing ball or annulus). 
Central to our approach is the \textit{alignment} of our neural model with a new variant of the classical $\varepsilon$-kernel technique from computational geometry. 
In particular, we develop a new relaxed-$\varepsilon$-kernel theory that maintains the approximation guarantees of the classical $\varepsilon$-kernels but with the crucial benefit that it can be easily implemented with \textit{bounded model complexity} (i.e, constant number of parameters) by the simple SumFormer neural network. 
This leads to a simple neural model to approximate objects such as the directional width of any input point set, and empirically shows excellent out-of-distribution generalization. 
Many geometric extent measures, such as the minimum enclosing spherical shell, cannot be directly captured by $\varepsilon$-kernels. 
To this end, we show that an encode-process-decode framework with our kernel approximating NN used as the ``process'' module can approximate such extent measures, again, with bounded model complexity where parameters scale only with the approximation error $\varepsilon$ and not the size of the input set. 
Empirical results on diverse point‐cloud datasets demonstrate the practical performance of our models.

Effective Neural Approximations for Geometric Optimization Problems
Samantha Chen
Oren Ciolli
Computer Science and Engineering University California, San Diego sac003eucad.edd
Computer Science and Engineering
University of California, San Diego edu
Anastasios Sidiropolous Computer Science and Engineering University of Illinois, Chicago sid sidiropo@uic.ed
Yusu Wang
Halıcroğlu Data Science Institute University of California, San Diego yusuwangeucsd.
Abstract
Neural networks offer promising data-driven approach tackle computationally challenging optimization problems. In this work, we introduce neural approxima- tion frameworks for family of geometric "extent measure" problems, including shape-fitting descriptors (e.g. minimum enclosing ball or annulus). Central to our approach is the alignment of our neural model with a new variant of the classi- cal e-kernel technique from computational geometry. In particular, we develop new relaxed-e-kernn theory that maintains the approximation guarantees the classical e-kernels but with the crucial benefit that it can be implemented with bounded model complexity (i.e, constant number of parameters) by the simple SumFormer neural network. This leads to simple neural model that approximate quantities such as the directional width of any input point set and empirically shows good out-of-distribution generalization. Many geometric extent measures, such as the minimum enclosing spherical shell, cannot be directly captured by e-kernels. To this end, show that an our aperoxiaproo NN used as the "process" module can approximate such extent measures, again, with bounded model complexity where parameters scale only with the approximation error and not the size of the input set. Empirical results on diverse point-cloud datasets demonstrate the practical performance of our models.
framework with
1 Introduction
Using neural networks to solve optimization problems in a data-driven manner has received great attention in recent years 9 45 19 30). However, challenge in using neural networks solve optimization problems is that their architectures often grow with problem size (3) The key question consider the design of practical neural models that both have the capacity approximate solutions to specific optimization problems with bounded model complexity (i.e. number of parameters independent of the size of input), and perform well in practice. A direction that has shown promise both theoretically and practically is neural algorithmic alignment [37] 38 44 (6), which intuitively informs architecture design via loosely imitating ("alignment" with) certain algorithmic frameworks to achieve improved accuracy and out-of distribuitti (OOD) generalization.
Our overall motivation is design efficient and practical neural models solve problems in data-driven manner. In this paper, we study this problem the context of a particular family of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

geometric optimization problems and demonstrate that biasing the model architecture towards some algorithmic flow yields more efficient and accurate approximations. a variety of point cloud descriptors, such as convex hulls, bounding volumes (e.g. minimum enc enclosing ball or ellipsoids), or best shapes fitting an input point set (e-g, the minimum-width slabs or spherical shells that cover an input set of points). These problems are called extent measure problems and are well-studied in computational geometry; e.g. [0 2 I 46 16 [ We show how biasing our model architectures towards a particularly well-known approximation technique known as the e-kernel [3 12 2 II] results in neural networks which can approximate the aforementioned point cloud descriptor with bounded model complexity, constant number of parameters which is independent to imput size.
particular, we aim compute
New work. In the high level. the type of geometric problems we consider have the following form: Given an arbitrary set of points P in Rd, the goal is to compute a certain geometric descriptor ju( P) for P. We want to train suitable neural network model that approximate ((P)) efficiently for any input point set P. We draw inspiration from an elegant line of work in computational geometry that approximately solves these problems using the e-coreset framework via e e-kernlls see Section for detailed descriptions. Our contributions can be summarized as follows.
Neural approximation of e-kernels. An e-kernel Q of a set of points P is a subset of P that approximately preserves the projection of P along any direction in Rd Once Q is given, one can approximate a family of geometric descriptors (c.g, the convex hull of P) by computing them using Q in time dependent only on [Q2 and not on [P). However, computing the e-kernel is not naturally aligned with common neural models for point clouds. We instead introduce alternative theory of relaxed-e-kernee guarantees while aligning naturally with the simple Sumformer [5] (a variant of DeepSets [47) This leads to an efficient neural model that approximates relaxed e-kernels with bounded model complexity independent of size of input point set P.
which retain the same approximation
Neural approximations of extent measures. Among the so-called unfaithful extent measures which cannot be directly approximated by e-kernels, a family of them can nevertheless be approximated via the linearization technique 4 In Section 4 we show that our relaxed- e-kernel can still be combined with the linearization technique to approximate such extent measures. We further employ to solve algorithmic tasks) where our relaxed e-kernel neural network will be used as the processor module. See Figure | This framework can approximate both faithful and family of unfaithful extent measures using only bounded model complexity.
saccode-process-dee
framework (introduced by [37]
Empirical performance. Importantly, we empirically demonstrate the accuracy (both in and out of distribution) and efficiency of the proposed neural models both for approximating e-kernels and several (faithful and unfaithful) extent measures (e.g. minimum enclosing balls/ / annulus) in comparison to both natural neural baselines and algorithmic approaches. Our Sumformer instantiated neural model consistently exhibits much stronger OOD generalization than Transformer -oommm--nstantiateed neural models for these tasks, which we think is partially due to the alignment of the Sumformer model with our relaxed-e-kerne algorithm.
In summary, the encode-pree process-decode framework instantiated with our relaxed e-kernel NN as the processor network is both practical and theoretically sound, and can solve family of geometric optimization problems accurately. Importantly, our models offer the advantage of being differentiable. enabling them to be used in downstream ML pipelines. Our neural approach also provides greater flexibility in comparison to classical algorithmic techniques: our framework can tackle tasks where the objective is hidden and only implicitly given via labeled examples. In contrast to classical algorithms which can not be used without knowing the target objective, our model can still efficiently learn the objective in data-driven manner, as long as the underlying goal corresponds to a variant of the shape-fitting problem (even when unknown).
Related work. This paper discusses efficient neural approximations of a certain family of geometric optimization problems on point clouds. As such, we will discuss relevant work related to neural point cloud processing and neural network approximations of general optimization problems. In particular, deep learning on geometric data especially point clouds - has advanced rapidly. Two foundational permutation-equivane models are DeepSets 47 and PointNet [28 29). Both DeepSets and PointNet have universal approximation guarantees; however, general universal approximation of permutation

---

clach
wioek
PC
Aax
Seau polia
Mias
A
Aaaz
duuc
(b)
Figure 1: Illustration of (a) kernel-approx-NN, and (b) our encode-decode-pee framework for approximating various extent measures. The processor module Wp can be frozen as pre-trained kernel-approx-NNN, and only encoder decoder needs to be trained in task-dependent manner.
invariant functions requires the internal latent dimension depend on the size of the input point se/ 12). In geometric deep learning, it is also common to use geometry-enhanced graph neural networks to process point clouds; see the proto-book S for comprehensive discussion. Recent work 24 14]
has seen a shift to Transformer based architectures for point cloud processing 48
In recent years there have been great interest in using ML help tackle combinatorial optimization problems; c.g. [39] 19 22 32 [3 31]. and surveys 7 9.. Theoretically, there are also several works on the best possible approximation guarantees one can get from these neural network approaches 31
23
45
17.. However, bounded model complexity usually is not guaranteed, other than which use hybrid algori-cc models. Our work uses neural algorithmic alignment
30
18
25
ideas 37
38
44 to develop practical neural networks with bounded model complexity.
2
Preliminaries
Transformers. A standard Transformer is the composition multiple Transformer blocks, each of which models seuueecceto-sequeeee permutation equivariant function using specific attention mechanism. For simplicity, below we introduce the formulation using just a single attention head: Given sequence X Rnxd (a length-n sequence of vectors in RR),, the output of single attention block T is another length-n sequence T(X) E IRaxd defined by
T(X) = MLP(X + Xtt)(X)XWv), where Attn(X) = softmax XittmaxxXXWaare (XWo
Here, WQ. WK. Wv Rddd matrices and MLP Rdd + Rd operates element- wise each of the n elements. (We fix the internal dimension to be d for simplicity of presentation.) Sequences for language tasks typically use positional encodings, e.g rotary PES [33], encode ordering information. However, since we are concerned with processing point clouds, each point in an input point cloud P has its coordinates in R4; hence we omit positional encodings. For Transformer with bounded complexity, i.e, total number of parameters is a constant independent of n, still takes ((n²) time per forward pass when processing an input point of size n..
Sunformers. A Sumformer (5] is a sequence-1o-scquence permutation equivariant model formed by composition of blocks defined follows:
Definition 2.1 (Sumformer Block). A Sunformer block is
function S X + y", such that for any length-n sequence X = [f,,...,.a In) E X", the output is another length-n sequence in y" defined by S(X) S([I,,.... xx,)) [1(21, Z)... (Z Z)}. where Z = Ei Ó(I;), o: X + gdd and v : X gd - y. Usually, both the input and output feature spaces are Euclidean: X pd and y da
Intuitively, at each layer, Sumformer block first computes a global representation of the input sequence via sum-aggregation (the quantity Z above), and then computes the individual representation of each input token from its initial encoding and the global representation Z via the function v (i.e, S(X) (x;, 7)). Conceptually, similar to the DeepSet architecture (47,, but each layer not necessarily a linear equivariant layer. Unlike the Transformer, the SumFormer takes linear
3

---

time per forward pass as computing Z takes (n)) time while computing each eb Z) takes only constant time, assuming d' and the dimensions of X and y are constant.
e-kernels and coresets. A classical technique in developing approximation algorithms for geometric problems is via the extraction of certain small representative subset of the input object, called e-coresets, and solving the problem only on the small subset. A popular coreset construction is via the e-kernels. First, given set of points P and a direction u E S with S denoting the unit-sphere in IRd, the directional interval w u (P) and directional width (P.) w.r.t. u are defined as:
W u (P) = "min (u, (u. p), max pi}: and (.(P) max p) -minuu 2u, p) = length of W. (P). PEP
PEP
PEP
PEP
Definition 2.2 (s-kernel), Given set of point P C R2, an s-kernel for Pis is a subset of points Q C P such that for any u E Sd-1, w. (Q) is an e-approximation of (P():: ie.. (1 (1- E),, S wa (Q).
Hence, an e-kernel Q of P approximates the width of P along any direction u. In this paper, we assume that any input point set P is contained within bounded compact set in R4; in fact, w.l.og.. assume each P is contained in the d-D hypercube Ca = of P consisting of all convex combinations of points in P. Our theoretical results in this paper will assume that each point set is not too "skinny", in the sense that it is "fat": A point set P C Rd is a-fat if there exist 0 < a S 1 and E Rd such that ō + aCa C CH(P) S 5 Cd-
Let CH(P) denote the convex hull
We now explain the utility of e-kernels for extent measures. An extent measure jl is a function that maps any point set P C Idd to a real value such that ((P")) S p(P) for all P' C P. Examples include the diameter of point set P, the minimum radius of any ball covering P (i.e, the radius of the minimum enclosing ball of P), the minimum width of any slab (parallel hyperplane) containing P, and the minimum width of any spherical or cylindrical shells containing P.
Definition 2.3 (Coresets and faithful extent measures). Q S P is an E-coreset for P w.r.f. if (P) S (1 ())(() An extent measure μ is faithful if there exists e >> Ouch that every e-kernel of P is a ce-coreset for μ..
Note that e-kernel is defined w.r.t. directional width; while E-coreset is defined for target extent measure. Intuitively, l is a faithful measure if any e-kernel of P serves as a valid e-coreset for P w.r.t. this measure μ.. Examples of faithful measures include diameter, smallest enclosing- ball radius, min-width of any enclosing slab, and bounding-box volume. For faithful measure μ., once an e-kernel Q is computed for P, evaluating nu() yields a e-approximation (pP) in time depending only on QQ) In short, computing e e-kernels leads to approximations of faithful extent measures. In the next Section 4 we will discuss approximations of unfaithful extent measures.
Motivating example. Before introducing our neural architecture, we provide a motivating ex- ample: the minimum enclosing ball. Given a set of points P C Rd. the minimum enclosing ball is the smallest-radius ball that contains all of P. In Figure 2
8.30
1.00
we compare two natural end-to-end neural network approaches, one using a Sum- former and the other Transformer, to directly predict the radius of the minimum enclosing ball from the input point set. We also compare with the algorithmically aligned encoder-processor- decoder network that we propose later in the paper. Each model is trained with point clouds of size 100 sampled uniformly from [-5, 5]2 and tested on point clouds of increasing sizes and bounding boxes (see Appendix for details). The error is shown on the left side of Figure 2 and we see that neither end-to-end approach generalize across sizes since the error grows rapidly as the size of the point cloud increases. In contrast, our encode- encode-process process-decode approach maintains low eтror across sizes as its error rate remains flat. On the right side of Figure 2 we see that our new encode mncode-process-deceee Sumformer (time complexity grows linearly), while Transformer grows quadratically. In what follows, aligns with the e-kernel and can therefore approximate
8:0
2506
cieeciia sine
Figure 2: Comparison of error (left) and inference time (right) of the Transformer, Sumformer, and encode-process process-decode approaches for estimating the radius of the minimum enclosing ball.
approach is as efficient as
we show how the secoodepprcess-deese extent measures with bounded model complexity.

---

Neural approximations of relaxed-s-kernels
The previous section states that for faithful measures, computing e-kernels leads their approxima- tion for any input point-set P. Hence intuitively, we wish to have a neural architecture to compute e-kernels. It turns out that existing algorithms construct e-kernels all require being able identify the exact extreme point(s) in various projects, which does not easily align with Transformer nor SumFormer. Instead, we will propose variant of the classical e-kernels, called the relaxed-e-keree which shares similar theoretical guarantees as s-kernels, We then develop a simple Sumformer-basee neural model that can efficiently approximate relexed-e-kernel with bounded model complexity.
Algorithm Relaxed-c-kernels
Require: P (pt..... . S Rd, k
1: Ω set of directions from Sd-1
Set MA. == max (A,) = max p)) pEP
2: Q x {
ReLU (u, P1) + EW ew(A)) ) - MA.)
for u E Ω do
ReLU p2) Ew -MAA)
4:
Ag + {(u,p) p P}
Pe (a(A
w(AA) t mmxxxx Au min Au
6: Compute Pc(Au)
(ReLU((,,p))) + ew (An) - -MaA)
qu t- (o
Let a R:R
R. such that
8:
Q.append(yu) end for
- -1
o(x)
10:
return Q
C 1)
(e
Figure 3: An algorithm for computing relaxed e-kernels. The functions Pe and are defined on the right. Notice that a is a modified softmax function.
3.1 Relaxed e-kernels
Definition 3.1 (Relaxed-<-kermel). Given set of points P Rd. a relaxed e-kernel is a set of points Q S CH(P) such that for any u E Sd-1, we have (1 (P=)) I w.(( (Q).
Unlike a standard e-kernel, where the output points must be subset of P, the relaxed-c-kernel allows each output to be convex combinations CH())). See Figure 4 for visualization. The key is to show the relaxed-e-kernels can replace e-kernels in approximating faithful extent measures. Indeed, this is guaranteed by the following theorem (through the relaxed e-coreset). The proofs in Appendix A.3.I] In addition to the relaxed-s-kemat we define an analogous reloxed-e-coreset and show that it has the same approximation guarantees for faithful measures μ.. Specifically, a relaxed e-coreset of w.r. is a set of points Q C CH(P) (versus Q P) such that (1 (1-t)n(() S ((P) s ()+))
input points (as guaranteed by Q C
max
(W.(P)
Figure 4: qu is the convex combina- tion of points in the shaded region.
Theorem 3.2. Let μ be a faithful measure with constant c. Let 0 < <. 1.
6e- There exists such that for any P, any relaxed e-kernel for P is a relaxed e' ecc-orreett for P.
A NN-aligned relaxed-s-kernel construction. A relaxed-s-kernel for P can be computed by Algorithm I Intuitively, we pick a fixed set of directions Q and for each u S2 we output a point qu 1Rd which is convex combination of points in P whose projections onto u are within (P) of the maximum. Pe (Aa) computes indicator vector for such points, and (a (Aw))) P then computes qu. where a is the modified softmax function described in Algorithm and qn. is a convex combination of the points in P.
Theorem 3.3 (proof in Appendix A.3.1) below shows that the quality of the output Algorithm depends the "fatness" of the input point set P. We also need to choose appropriate set of
5

---

directions S2: in particular, 92 is a az net for all possible unit directions S Note that a set A is 4ya
8-net of metric space (X, dx) if A X and for any point X, there exists A such that dx (z, a) < 6. It is easy to construct ô-net of s of size 0(1/8d-1) where the distance between two directions is measured as the angle between them.
Theorem 3.3. Lel P 11-1,11 be a o-fat point set and let 0 < & < 3. Suppose 22+ is an ar ava
net
for sd-1 s.t. [2]] = 0 W
Let St = {-u : u E } and let = 1 Srt so for all u E S2 -u Q. Then the set of points Q constructed via Algorithm ii a relaxed-3e-kemnel of P.
3.2 Relaxed-e-kernel approximating NN architecture
Given arbitrary point set P C Ca. we will represent P Rxd sequence of d-vectors where N = IP. Given X E Nx let Gool denote column-wise application of the modified softmax normalization described in I we apply a to each column in X). First, introduce general neural framework of specific form: given P E R xd, it will output & points in R4; that is, No. (P) E R as follows:
No. (P) = Goo (o:
(I)
where Φe is a santenne-to-sequenee permutation equivariant model that maps a sequence of points in R to a sequence of points in R Note that regardless of the length of the input sequence P (i.e., N), the output No. (P) is always in Rg viewed as points in Rd The model Φ can be instantiated with any permutation equivariant neural network: such as Sumformer S. or a Transformer Te- The resulting final model No. is then denoted by Ns. (P) = (P)) for the SumFormer instantiation or Nr. (P) = col (Te P for the Transformer instantiation. See Figure | (a). We will use the Sumformer implementation Nss. the following result shows that this simple model is sufficient to align with the computation of a relaxed-e-kerne.
Theorem 3.4. Given any E, O, there exists SumFormer Se with only single block, and bounded model complexity (depending only on 6, O and the input dimension d) such that, for any o-fat point clouds P c Rdd of arbitrary size, Ns. (P.(P) (P) is relaxed-e-kerie for P.
Intuitively, the SumFormer SpP) E RNN can easily simulate the computation of the collection of Pe(Au)'s, for all k number of u E Ω in Algorithm I Line of Algorithm [ is then computed by the outer columnwise-softmax normalization as in Eqn. 1 thereby outputting l points in R. which form a relaxed-g-kerne for input point set P. We refer to the neural network model Ns. in Theorem 3.4 as our relaxed-s-kerell -eeeedaapprooiimttin--eeee
network, abbrev. kernel-approx-NN.
With our kernel-approx-NNN, it is now easy to construct a cooplex-complexity neural network to approximate faithful exient measures. Consider any faithful extent measure μr: For any input point set P. once we are given a belllaxdd---keeeee Q of P. we can simply compute u(Q) as an approximation of (PP). By Theorem 3.4 the points No. (P) E R form a relaxed-e-kernel of P, for suitable depending on the output size k. By Definition 2.3 we can compute (N,, (P)) as an approximation of function as its output does not change
((P). Note that a can be viewed as a permufation-invarian as the ordering of input points change. Hence we can use DeepSet architecture [47 to approximate weaall--mauuuupprraa
NN as Nisichtul (P) = Nedepseer (No, (P)). μ: in particular, we set our approximators for permutation-invarian functions where the model Deepset models are universal complexity depends on the maximum input size (e.g, 44 34] in our case, the input is of size k x d (k points in Rd computed by our cemee--pprox-coo NN Ns., ). Hence the model complexity of Nddepset is also bounded, depending only k. thus only on E, a and d, and not on the size of original input point set P. Indeed, the following corollary implies that we have NN with bounded complexity that can approximate extent measures such as diameter, radius of minimum-enclosing ball, and width of minimum-widh slab, for input point set of arbitrary size.
Corollary 3.5. For any & > 0, > O and faithful extent measure with constant c as in Definition 2.3, there exists founded-complenes NN of the form Ntainiial (P) Nacoppot (No, (P)), such that for any a-fat point set P, the oulput N Nistiaal (P) satisfies that:
(1- - (c3c)))(PP) &Nestchhu $ (1 (C)) +

---

(4)
Figure 5: (a) Upper/ lower envelopes and the extent vector for a family of linear functions. Thick curves in (b) form an e-kerne G of and those thick curves in (c) is a relaxed-e-kerne Dashed lines those in F. Note that, unlike (b), a relaxed-e-kernel does not need to be subset of F.
Neural approximations of unfaithful extent measures
The e-kemnl framework can also be used to derive efficient approximations for a certain family of unfaithful measures via the co-calle""imeerrzante
trick (2]. We briefly describe the high-level idea, which follows the same framework as (2). We will show that our relaxed-e-kernel can replace the role of e-kernel in this approach. First, we need define (relaxed-) (aaxxed-ee-keee Je-kennlls for sets of functions (instead of points). The way to handle those unfaithful extent measures is to first convert them to linear functions via the linearization technique. Specifically, given a set of real- valued functions F = (fi,..., fn Rd-1 + JR. its upper envelope is the function UF Rd-1 R where (2)2) = ma fIx), while its lower envelope is defined by Ly(x) (2) = min f(x). Definition 4.1. Given ser of fianctions J (fi.....,fh,, where fi Rd-1 R, its extent is (x( = Ux( (x( and its extent-interval is {x(x)= { An s-kernel F a set G C F such that Eg 2 (1 E)
See Figure 5 We define analogous concepts for relaxed-e-kenee Given two intervals 1 = |a, b] and 12 = |c, dl, the Hausdorff distance between them equals maz cl, b d|}. Definition 4.2 RRelaxed-e-kernel for sets of functions). A relaxed e-kernel for F is a set 9 of functions (not necessarily subset of F) such that for any E Rd-1, we have that (i) E c((x)= S E =((x) and (ii the Hausdorff distance between E ((()) and E x(x) is at most E Ex)
Now consider linear function fxx 2 + +... - + ags where x [2 [ Fz-1 IT Rd-1, This linear function represents hyperplane in Fd. Its dual the point f := (a], ........ adl e
Rd Symmetrically, given a point p (pi.-... ma E TR. its dual hyperplane is the linear function let
p (x) = P1 + P + Pa- Given a set of linear functions F = -ft....,, F = (f...., }i] C IRd denote its dual point set. Note that (f*)* = f and (F*)* =
Theorem 4.3. G is relaxed e-kernel for the set of linear functions F if and only if is a relaxed E-kernel for the point set F²
Often we want to find the extent or e-kernels for sets non-linear functions. Depending on the functions, it is possible to linearize them as follows (2): Suppose F is set of (d + p)-variate polynomials F {f((z) = fxr a.) E [N], Rd E RT). We say that F admits a linearization of dimension m there exist p-vriitte polynomials vo...., tmm
IR - and
d-variant polynomials .p,,..., ipm IR + R such that for each fi, we can write it as
fa(x) = fa, a;) = va():)) + u/ (1(a))(((z) + + the ())))))mm))).
Now define functions T R + mm+1 and क Rd - mm+1 as (a) = [No(a)........ Um (a)) for any a E RP and (xx) = [1, 42) (x),
(x) for any x E Rdd Then we can view Ji as new linearized form [2z a;) (a.) 2 ((x) in space m=+ For standard e e-kernels, finding the e-kernel for the dual of the set of linearized functions gives an e-kernel for the set of original functions. In also construct relaxed-e-kemet for a set of functions F from an
Theorem 4.4 we prove that e-kernel of the dual set after lincarization.
Theorem 4.4. Suppose F is set of N number of (d + p) -)variiate polynomials which admit linearization of dimension m; i.e. there is a set of A (aI,..., aN) C RP, V RP + Rm++1 a, A, E [N], and the dual F = (a:) : E [N]]. Let O: C gm+1 be relaxed-e-kemel for F of size k computed via Alg. I. Suppose Ø = (ar) +... + + V(x)) :j 14 1, 2 0}. Then the set of functions Q (z)) 23) is relaxed-e-kenne for the original set of functions F.
and Rd m1 such that F {f((z)
((a,)TT
7

---

Finally, as shown in [2), a family of unfaithful extent measures can be transformed to finding the smallest extent E = _ of set of N functions F(constructed from the input pointset P with N = (PD) that admit a linearization, and thereby can be approximated by computing the smallest extent of the relaxed-e-kernel Q. as computed in Theorem 4.4 Once 2- is computed, finding the smallest extent & takes time only depending on [2sl and indepent to the original pointset size P. We provide an example in Appendix [A.2 of how relaxed-s-kerneh can be used to approximate the width of the minimum enclosing annulus for point cloud.
Neural framework for approximating unfaithful extent measures. In order to approximate those unfaithful extent measures that can be solved via linearization, we make use of the encode process- decode framework proposed in [1S]. Given X' which the space of point clouds. point cloud P E X, and an extent measure j : X + R", we define
N Nextent (P) = (N((N
Intuitively, given a size-N pointset P E Rx- the encoder N= E (x(+1)+1 computes the linearization which maps P to size-N (dual) point set in R The process-network Np then outputs a size-k relaxed-e-kernel, and the decoder ND network computes the final approximation of the extent measure. Importantly, for the process-network Np, we use our s-kernel approximating neural network No. defined in Equation (1 and given P = (P)(P), the output of processor Ap P) [x((m+1) is size-k relaxed-e-kernd for P. See a visualization of this architecture in Figure and framework from our motivating example in Figure 2 Note that the encoder WE can be any permutation equivariant architecture. In our experiments, we simply apply an MLP to each element of P so NE ((P1........................(( PND) [ML((1)..... MLP(PN) (MLP )]- The decoder ND can be implemented by any universal permutation invariant architecture. In our experiments, we use DeepSet as the final decoder, ND. to compute the final approximation of the extent architecture. Note that we can also use Nextennt to approximate faithful extent measures as NE can be set to the identity function. In our experiments, we use this recoder-process-deeee Nextent to approximate both faithful and unfaithful extent measures.
note that this exactly the mucode-process--ee
5 Experiments
We evaluate both our kemnel-pppro--NN (cf. Eqn. I to approximate relaxed-e-kemeels as well as our peoode-process-deoode framework (cf. Eqn. 2 for extent measure approximation tasks (faithfuul and unfaithful). Throughout this section, we report the best results after a hyperparameter search. All details regarding training and datasets are given in Appendix A.4
Our experiments use (i) two synthetic datasets 'Gaussian Mixture' (point clouds from 2 to 5 random Gaussian clusters), and 'Mixed Synthetic" (a mixture of synthetically generated point clouds, including 'Ellipse", 'Gaussian Mixture' and more), and (ii) two real datasets, SQUID 26 (2D point clouds generated from boundary contours of fish) and the 3D ModelNet [43. In the main text, we present average evaluation metrics over all test data; the Appendix provides complete results, including standard deviations, and further experiments demonstrating that fixed-size models continue to perform well on OOD point sets (across varied sampling schemes and sizes).
Relaxed-e-kernel approximation. We examine the performance of the kernel-approx-NN -N (cf. Equation using both Sumformers and Transformers as &e in No,; and we denote these different instantiations as S. and Te, respectively. We also compare against direct neural baseline that directly outputs a coarsened point cloud aggregating encoded point features and passing the result through an MLP to produce the final output point cloud. The Sumformer and Transformer implementations of this baseline are denoted ScB and Te,B, respectively. We also include a comparison to the classical e-kernel and our relaxed s-kernel algorithms, both with respectively, For performance, we use the directional width error to measure the error caused by our approximation: Edit (P, Q) max
0.1, denoted B.,E and BAR,. R,
|ww. (M)(P)--o)) (Q)) where P is the input point set, Q is the output (P.))
of our kemnel-appro--oe -NN, and 52 is set of 1000 random directions. We report results for datasets in R and in 3R33 in T Additional results for point clouds in R as well as many other experiments including effects of hyperparameters (e.g. width of latent dimension), are given in the Appendix. Overall, using Sumformer instantiation S, as No. consistently yields lower emror on OOD data than the Transformerrinsttantaaaoo T. This gap is most striking on real world datasets: when trained on the synthetic datasets (" ('Mixed Synthetic or GGasssian Mixture') ), the S. has significantly lower error
8

---

Table I: Edit for predicted relaxed-e-kernels of size 16 and 64 respectively, for point clouds R (left) and IS (right) across three different test sets for each train set. 'In-dist.' refers to in-distribution test sets. "Mixed Synthetic" has no "OOD, Synthetic" because the train set contains all types of synthetic data. Similarly, the models trained on SQUID and ModelNet are not OOD those test sets (so unreported). Since algorithmic baselines do not require training, they have no 'In-dist' error. Boldface indicates the lower error (better accuracy).
Test Sets
Test Sets
OOD
OOD
Train Set
Method
In-dist.
Synthetic
SQUID
Train Set
Method
In-dist.
Synthetic
ModelNet
S.
0.014
0.043
0,028
S.
0.047
0.039
0.064
Gaussian Mixture
T
0.027
0.097
0.218
Gaussian Mixture
T
0.054
0.066
0,250
S.B
0.146
0.146
0.962
S.B
0.274
0.223
1.949
Tz.
0.190
0,383
0.94
Tz.
0.357
0,803
5,514
S-
0.028
0,504
S.
0.041
0,099
T,
0.061
0.400
T
0.049
0.265
SQUID
ModelNet
S. B
0.421
7.137
S. R
0,379
0.528
Tzn
0.228
14.561
Te,n
0.542
0.581
S.
0.027
0.065
S:
0.035
0.055
Mixed Symthetic
Te 0.032
0.296
Mixed
T
0.042
0.117
S.B 0.094
0.97
Synthetic
S.B
0.174
2.288
T.D
0.203
0.939
Te,8
0.289
4.356
Algoritumic
B,,
0,180
0.228
Algorithmic
B.R
1.016
2.176
Baselines
B,
0.040
0.062
Baselines
B..6
0.062
0.050
than Tg when tested on OOD samples from SQUID (in RR2) and ModelNet (in )R While Tg also has the capacity to implement Algorithm we believe that the simple and more direct alignment of S. with this algorithm leads to faster training (optimization) and better (OOD) generalization.
Approximating extent measures. We train the encode- process decode model (Eq. 2 to predict three extent measures: radius of minimum enclosing ball (MEB), radii (and therefore area) of minimum enclosing ellipse (MEE), and width of minimum- wiittuu--witth annulus (MEA) covering input points. The first two are faithful extent measures, while the last unfaithful. We compare two instantiations of the general model Noxtent: (i) Soxtent when using the Sumformer within the processor model Np, and (ii) Textent when using the Transformer.
To examine the contribution of the relaxed-e-kernel module when used as No., we compare two training protocols: (1) full end-to-end optimization of the entire pipeline (denoted as 'E2E') and (2) regime in which the inner -amnel-pproo-NNN is fixed after being pre-trained to output a relaxed-s- kernel (denoted as 'Frozen'), ) and then only the encoder and decoder are trained based on the specific in the processor module, we also construct baseline where we do not use Equation I to compute a coreset. Instead, we use the output de (P) (where P = NE (P) and feed it to the decoder ND. SBaseline and Taaseline to denote the Sumformer and Transformer instantiations of this baseline model. Additionally, we also compare against the proposed direct neural approximations described in Section 2 with Sumformer and Transformer implementations denoted Spirect and Tiirett- An extended comparison to classical algorithmic baselines in terms of both accuracy and runtime is also included Appendix [A.4]
task. To understand the effect of mapping input point to a relaxed-e-
The results for all three extent measures are shown in Table andd we evaluate the performance as follows: (1) For MEB, we measure the relative error &, of predicted minimum-radin over the true optimal. (2) For MEF, we use the relative errors of both predicted major and minor radii (denoted as Exmaaj for the major radius and E,,in for the minor radius). (3) For the MEA, we use the relative error for the predicted smallest width Ew, To measure the quality of our returned geometric shape, also compute& Ep. the percentage of input points not covered by these approximations. These results are in the Appendix and usually this portion is very small (around 1-2%).
All results in Table are for di-distribution test sets: e.g, if they are trained on SQUID, then the test sets are also from SQUID. The term "Synthetic" in Table Yable[]refer to different datasets for different tasks (see Appendix for details). From Table we see that in almost all cases, "Sextent (Frozen)" achieves the best result (lowest error). In general Sumformer versions outperform corresponding Transformer versions, which is suggestive of the benefit of the alignment (resemblance) of Sunformer- instantiated kernel-approx-NN with Al Algorithm|] T
In the case of Sumformer versions of neural models,

---

Table 2: Error metrics across MEB, MEE, and MEA (standard deviations Appendix). & relative radius error of MEB E,,iin / maj minor/major radius eтrors of MEEs E error in MEA width. Boldface marks the best (lowest) value each column.
MEB
MEE
MEA
MBE
MEA
Train Set
Method
3,
Ex,min
Erama
Eur
Train Set
Method
&
Eyami
Ex,may
Sustent (Frozen)
0.009
0.037
0.022
Susten (Frozen)
0.017
0.056
0.047
0.073
Seatent (E2E)
0.023
0.056
0.047
0.038
Sedent (E2F)
0.010
0.078
0.050
0.087
Texteu (Frizen)
0.099
0.041
Texteu (Froven)
0.068
0.058
0.064
Synthetic
Testeme (B:26)
0.024
0.028
0.022
0.077
SQUID
Texment (E2E)
0.190
0.093
0.045
0.104
0.048
0.378
0.674
Stseelne
0.027
0.322
0.250
0.191
Taudine
0.030
0.071
0.047
0.417
Tiaseline
0.039
0.357
0.049
0.118
Spioet
0.126
0.033
0.038
0.141
Spieod
0.050
0.68
0.05
0.041
Trirect
0.178
0.932
0.887
0.079
Thirect
0.685
1.269
0.188
0.065
Minimum Enclosing Boll
Minimum Enclosing Ellipse
Minlmum Enclosing Annulus
Scmel
Point
Point
Point
Satert (1 (Froown)
Sutirr (E22)
Tacura (Prozen))
Tixti (826]
Sauetion
Toun:
Figure 6: Size generalization across all extent measure tasks. We record the error for each model on extent measure tasks as the size and bounding box of the input point cloud increases. Our frozen Sextent model consistently outperforms all other neural baselines across every task.
the "Frozen" version (where the processor module is pre-trained then frozen, and only the encoder and decoder will be trained in task driven manner) is usually much better than the "E2E" version. This advantage, however, is less clear for the Transformer based models. Finally, while the direct models outperform our models terms of E for MEA on the SQUID dataset, refer to Table [5 in Appendix to see that our models achieve more geometrically faithful predictions, reducing the proportion of excluded points by approximately one third.
Additionally, we examine how each model's error changes as the size of the input point cloud increases (i.e., its size generalization capability) across all extent-measure problems in Figure 6 Each model in this experiment is trained on synthetic data generated from within the bounding box [-5,5]2. For the test data, we simultaneously scale both the number of input points and the size of the bounding box from which each point cloud is sampled. Extended details for the experiment set-up are in Appendix A..4 The results in Figure Figure/Jlightt Ghighhighh the advantage of the kernel-approx-Nyy NN as the "Sextent (Frozen)" has much better generalization as compared to all other neural models. Visualizations of the solutions in Figure [4] (Appendix (A.nndixxA.4)... for in-distribution and nut-of-distribution data for each problem even more suggestive of how aligning the processor network explicitly with relaxed-g-kernel can better adjust to OOD data.
6 Conclusion and Limitations
We introduce an alternative theory of relaxed-z-kernlls which we show naturally aligns with SumFormer-basee architecture to approximate family of faithful and unfaithful extent measure problems using bounded model complexity. Empirically, we demonstrate the benefits of alignment of our SumFormer instantiated models and the effectiveness of our limitations include: The chitecture, especially in better OOD generalization performance. Some model complexity still depends on the dimension (but not the size) of the input point sets. Also our theoretical results depend on the "fatness" of the input point sets. Nevertheless, our work shows the benefits of neural-algoritheg interplay between task structure, classical algorithmic approaches, and network design yields better performance, both theoretically and empirically.
ar-
alignments and opens the door to further explorations of how the
10

---

7 Acknowledgements
This work partially supported by NSF (National Science Foundation) by grants CCF-2112660 as well as a NAIRR Pilot Project NAIRR250087.
References
[1] Pankaj K. Agarwal, Boris Aronov, and Micha Sharir. Exact and approximation algorithms for minimum-wiie width cylindrical shells. Discrete & Computational Geometry, 26:307-320, 2001.
[2] Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. Approximating extent measures points. Journal of the ACM (JACM), 51(4):606-635, 2004.
[3] Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 52(1):1-30, 2005.
[4] Pankaj K. Agarwal and Jirí Matousek. On range searching with semialgebraic sets. Discrete & Computational Geometry, 11(4):393-418, 1994.
[5] Silas Alberti, Niclas Dern, Laura Thesing, and Gitta Kutyniok. Sumformer: Universal Ap- proximation for Efficient Transformers. In Topological, Algebraic and Geometric Learning Workshops 2023, pages 72-86. PMLR, 2023.
[6] Gill Barequet and Sariel Har-Peled Efficiently approximating the minimum-volumm bounding box a point set in three dimensions. Journal of Algorithms, 38(1):91-109, 2001.
[7] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon, European Journal of Operational Research, 290(2):405-42) 421, 2021.
[8] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometrie Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. CoRR, abs/2104.13477 2021.
[9] Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1-6) 2023.
[10] Timothy M Chan. Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. In Proceedings of the sixteenth annual symposium on Computa- tional geometry, pages 300-309, 2000.
[11) Timothy M Chan. Faster core-set constructions and data stream algorithms in fixed dimensions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 152-159, 2004.
[12] Nadav Dym and Steven Gorter. Low-dimensional invariant embeddings for universal geomet- ric learning. Foundations of Computational Mathematics, pages 1-41, 2024.
[13] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 1558000--5,52, 2019.
[14] Meng-Hao Guo, Jun-Xiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R Martin, and Shi-Min Hu. PCT: Point cloud transformer. Computational visual media, 7:187-199, 2021.
[15] Jessica B. Hamrick, Kelsey R. Allen, Victor Bapst, Tina Zhu, Kevin R. McKee. Joshua B. Tenenbaum, and Peter W. Battaglia. Relational inductive bias for physical construction in humans and machines. In Proceedings of the Annual Conference of the Cognitive Science Society (CogScí), pages 1773-1778, Madison, Wisconsin, USA, 2018.
[16] Sariel Har- Peled and Yusu Wang. Shape fitting with outliers. In Proceedings of the nineteenth annual symposium Computational geometry, pages 29-38, 2003,

---

[17] Yu He and Ellen Vitercik. Primal-Dual Neural Algorithmic Reasoning. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj. Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 22743-22766. PMLR, Jul 2025.
[18] Andrew B Kahng, Robert R Nerem, Yusu Wang, and Chien- Yi Yang. NN-Steiner: A mixed neural-algorithmin approach for the rectilinear Steiner minimum tree problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13022-13030, 2024.
[19] Elias Khalil, Hanjun Dai, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[20] Diederik P Kingma. Adam: method for stochastic optimization. arXiv:1412.6980, 2014.
arXiv preprint
[21] Piyush Kumar and E Alper Yildirim. Minimum-volume enclosing ellipsoids and core sets. Journal of Optimization Theory and Applications, 126(1):1-22) 2005.
[22] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. Advances in Neural Information Processing Systems, 31:537-546, 2018.
[23] Andreas Loukas. What graph neural networks cannot learn: depth width. arXiv preprint 1rXiv:1907.03399, 2019.
[24] Dening Lu, Qian Xie, Mingqiang Wei, Kyle Gao, Linlin Xu, and Jonathan Li. Transformers in 3d point clouds: A survey. arXiv preprint XxXx:22055.07417, 2022.
[25] Evan McCarty, Qi Zhao, Anastasios Sidiropoulos, and Yusu Wang. NN-Baker: A Neural- network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs. In Advances Neural Information Processing Systems, volume 34, 2021.
[26] Farzin Mokhtarian and Sadegh Abbasi. Shape similarity retrieval under affine transforms. Pattern Recognition, 35(1):31-41) 2002.
[27] Jeff M Phillips. Coresets and sketches. In Handbook of discrete and computational geometry, pages 1269-1288. Chapman and Hall/CRC, 2017.
[28] Charles R. Qi. Hao Su, Kaichun Mo, and Leonidas J. Guibas. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pages 77-85. IEEE Computer Society, 2017.
[29] Charles R. Qi, Li Yi, Hao Su, and Leonidas J. Guibas. PointNet++: Deep Hierarchical Feature Learning on Point Sets in Metric Space. In Advances in Neural Information Processing Systems (NeurIPS), pages 5099-5108, 2017.
[30] Chendi Qian and Christopher Morris. Towards graph neural networks for provably solving convex optimization problems. arXiv preprint arXiv:2502.02444, 2025.
[31] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation Ratios of Graph Neural Networks for Combinatorial Problems. In Advances in Neural Information Processing Systems, volume 32, 2019.
[32] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, David L. Dill, and Leonardo de Moura. Learning SAT solver from single-bit supervision. In Proceedings of the Interna- tional Conference on Learning Representations (ICLR), 2019.
[33] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, Neurocomputing, 127063, 2024.
12

---

[34] Puoya Tabaghi and Yusu Wang. Universal representation of permutation invaarian functions on vectors and tensors. In 35th International Conference Algorithmic Learning Theory (ALT), 2024.
[35] The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 6.1 edition, 2025.
[36] Petar Veličković, Adrià Puigdomênech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The CLRS algorithmic reasoning benchmark. In International Conference on Machine Learning, pages 22084-22102. PMLR, 2022.
[37] Petar Veličković and Charles Blundell. Neural algorithmic reasoning, Patterns, 2(7), 2021.
[38] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural Execution of Graph Algorithms. In International Conference on Learning Representations.
[39] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[40] Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Michael A Osborne, and Ingmar Posner. Universal approximation of functions sets. Journal of Machine Learning Research, 23(151):1-
56, 2022.
[41] Changshuo Wang, Meiqing Wu, Siew-Kei Lam, Xin Ning, Shangshu Yu, Ruiping Wang, Weijun Li, and Thambipillai Srikanthan. GPSFormer: A global perception and local structure fitting- based transformer for point cloud understanding, In European Conference on Computer Vision, pages 92.9..66 Springer, 2024.
[42] Xiaoyang Wu, Li Jiang, Peng-Shual Wang, Zhijian Liu, Xihui Liu, Yu Qiao, Wanli Ouyang, Tong He, and Hengshuang Zhao. Point transformer v3: Simpler faster stronger. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4840-4851, 2024.
[43] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d ShapeNets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1912-1920, 2015.
[44] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What Can Neural Networks Reason About? ICLR 2020, 2020.
[45] Morris Yau, Nikolaos Karalias, Eric Lu, Jessica Xu, and Stefanie Jegelka. Are Graph Neural Networks Optimal Approximation Algorithms? Advances in Neural Information Processing Systems, volume 37. Neural Information Processing Systems, 2024.
[46] Hai Yu, Pankaj K Agarwal, Raghumath Poreddy, and Kasturi R Varadarajan. Practical methods for shape fitting and kinetic data structures using core sets. In Proceedings of the twentieth annual Symposium Computational geometry, pages 263-272, 2004.
[47] Manzil Zaheer, Sahand Kottur, Anima Ravanbakhsh, Barnabás Poczos, Ruslan Salakhutdinov, and Alex Smola. Deep Sets. In Advances in Neural Information Processing Systems, volume 30, 2017.
[48] Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun. Point transformer. In Proceedings of the IEEE/CVF international conference on computer vision, pages 16259-16266 2021.
13

---

A Technical Appendices and Supplementary Material
A.1 Additional details from Section
Here, provide more details regarding the computation of e-kernels. One simple algorithm to compute an e-kernel is given in Algorithm More sophisticated methods can found [10] and [46] but highlight Algorithm as it is most similar to the computation of the relaxed-e-kenee Section 3.2] In summary, one may compute an g-kernel by carefully choosing a set of directions Q and choose points according the max-projection in that direction. We show the correctness of this algorithm in Theorem A.3 However, we first provide some auxiliary lemmas which we will use in the proof of Theorem
in
A.3 well subsequent proofs.
Lemma A.1. If P is or-fat point set, then for any E
Sdd11, w.(P) 2a.
Proof. Suppose P is an a-fat point set so aC C CH P). For any S and p E CH(P), (u.p) ||l|||e|| Since aC S CH(P). ||p|| 2 a so (u. p) 2 a and maxpep p) 2 a. Furthermore, minpep (u, P (u, m -u,
u. p) I -a. Then
(a(P) max(u, min u, p) 2 2a pEP
PEp
Lemma A.2. Let S S Ca. Given two unit vectors u, ut E such that I|u r'll S x, wu( 2 (5) 22yd
Proof. Given any S.
[x, (z, ud'l = (uu ui, æ>) S I||u - w1|||=||| S Avd.
where the final vd because x E [-1, 1]dd Then
w. (5) = max (u', s) - smin(u',.)
#ES
s,E3
(nd, argmax,es (u,, 8)) min(w' .8)
#ES
M. (u, argmax,est 8)) Avd
min(u', (u',
sES
M (u, argmax, (u, 8)) Avd
(u', argminsss s))
(u, argmax, EEs (u, 8)) - Avd ((u, algargmnn (u, 8)) + XVd)
(u,
w.(S) 2Avd.
Theorem A.3. Let P C C [1, be a-fat point set and let 0 < E 33- Suppose Q is
4ya -ea-net for Sd-1 so |0 = O (10) ) Vu, u' St I|u u'll S (يوي) and for all Ω
-u Ω. Suppose that Yu Ω -u Ω. Then the set of points Q constructed via Algorithm an e-kernel for P.
is
Algorithm 2 Computation of e-kernels
Require: CC Rdd_ k Ω is set of k: directions
Initialize Q == (
for Ω do
Qaappnn((rrgmax,cpll
end for
return Q = (qu E 2}
14

---

Proof of Theorem A.3 Let E Sa-1 Let X = oz
Since 0 is an X-net for s there is
4 u' E 52 such that u u S X. Therefore, by Lemma A.2
(i((Q) w. (Q) 22vd2 W. (P) 22vd w.(P) 4\vl.
Therefore.
Wa Q
4Avd
4Avd
-
Wa
W
a
where the second inequality comes from Lemma
A.1 Thus, (Q) 2 (1 E))
A.2 Additional details from Section
We provide example of how relaxed-e-kemells enclosing annulus. However, we will first need show in Theorem AA55 Theorem 1.4/can be used compute glaxed-e-kernele for fractional powers of polynomials. Our proof of Theorem A.5 builds on the following lemma, originally proved by (2)
be used to approximate minimum width
Lemma A.4. Let 0 < E < be parameter, 2 2 and let ó (s/2(r 1))". we have 0 H a < A < < and B 2 (1 0) a). then
B²/r A/rr 2 -1-288 -)b-))
Theorem A.S. Let F. be a family of (d + p) variate polynomials which admit a linearization of dimension m as Theorem 4.4 Additionally, suppose for every fs. f((x) 2 0 for all Rd Let
r 2 2, 6 (r/2(r (r 1))", and let g = {gi} be a relaxed-ò --kmmell of F. Then 9 = {9; 1/r is relaxed-e-kernee of F1/1 = {$-
Proof. Let = (e/2(r - 11y² where r 2 is an integer. Let be relaxed-6-kernel of F so E((x) C Ex(x and & c(x) is within 8 (x))--aaddoor distance of E E((x). Since F is positive, for any a E Rd, we know that
0 min(x) S min(x) S max (1) S max(x). fEF
geg
vEg
fEF
Additionally, by the definition of relaxed-e-kemels, ()ax/e=F)() mmineer())). Then, we apply Lemma A.4 to get
max g(x) mingeg g(x) 2 (1
max g(x)1/r min g E (1)rg(x) (1 e)( max 9E91/r
f(x)
min
faa)
gEFi/r
SEFip
Now, we are prepared to provide an example of Theorem A.5
can be used to approximate minimum
enclosing annulus for points in RR2 Given = {PI..... .PN.
PN
C R22 and any x TR? finding the
width of the minimum enclosing spherical annulus centered is
w(z, P)
max | pll
min PEp
I pll
Per
We define the of functions F (f | pll p P}. Notice then that Ex(x) = w(x, P) and the width of the minimum enclosing spherical shell is exactly mingeRs Ex(x). Similarly, the optimal center for the minimum enclosing spherical shell is (rgmin)ege&F(()) By Theorem A.5 {||= pll E P) translates to relaxed-e-kemel for F.
relaxed-e-kernel for F
Suppose (01, x22) E R22 and pt (pr,1, Pi.2) E R2 where pa E P. Given fi E FF. of + 2 2p,,131 2pr.202 + p + pi admits linearization of dimension follows:
(o())) pi, pl vi (p:) -pp.,1 (p:)) -2p.2 (b)(p)) =1
(x(x) = #1 (2(x) x2 pa(x)) = 2 +
By Theorem 4.4
for the dual space via Algorithm in R and map back to relaned-e-kernel for F' Qe. Then Qe,1/r is a relaxed-e- for F by Theorem A.5 Computing min Eg.,// (x)) as well as argminggga&2... (x) outputs the width and center of the minimum enclosing annulus, respectively.
compute relaxed-e-keen
15

---

A.3
Proofs details
In this section, we will provide the missing proofs from the main text.
A.3.1 Proofs from Section
The following lemma will be important to show that relaxed s-kernels can approximate well-behaved measurements of the original point set P.
Lemma A.6. Suppose Q is relaxed-s-kernel of Let P PUQ. Then (a) Q a e-approximation of P and (b) an e-approximation of P.
Proof of Lemma A.6 that
Let W S To show that Q is an E-approximation of P, must show
max u) eQu(Q) max u) max u) (Q) 4EQ
peP
qEQ
and
min u) -ew S min (p, u) S min(q. u) =Qu qEQ
PEP
QEQ
We know that max (D, u) = maxxmaa u), max,co u)}. We know that max (g. u) - (Q, S maxpep (u. < max (u, q) + ew,(Q) because Q is an e-relaxed- kernel of P. Clearly, max (g. u) EW,, (Q) S max (q, u) S max (g. u) (Q) so
max u) - (Q) S max(max(m u), max (g, u)} max u) max u) + (Q) gEQ
qEQ
peP
qEQ
PEP
We can do something similar for mint (u u) and min (D, u).
The same argument will hold for (b).
Proof of Theorem 3.2. Let p = QUQ. Let μ be faithful measure and let e be the constant in for the faithful measure, μr. By Lemma A.6 (a), Q is e-kernel of P. meaning Q is ce-coreset of P. By Lemma (b), P is e-kemne of P. meaning P is a es-coreset of P. It then follows that
1 CE 1 cs ((Q) < ((P)
1 1 CE
1 C5 (Q)).
For es < 1/3,, is easy to verify that this implies
(1 - (133c))(())) S u(P) & (1 3cE ((Q),
hence the theorem holds with c' 3c.
Proof of Theorem 3.3 First, we make two important observations regarding the points in the output relaxed-e-kernels, Q, computed by Algorithm [ and their relationship to the set of chosen directions Q. First, suppose we are given > 0 and A {ai,..., ax ( } C IR such that a, (u,P.).
let [di,...,ay]] Recall from Algorithm Ps is defined as
ReLU a + E w(() - Ma)
ReLU (22 8 w(A) Ma)
(a(a)=
RcLU((a, + E w(A) - MA)
where MA = max(AA and w(A) max(A) min(A)) A). Note ReLU(a; + + (A)) > 0 only when o; is within e (((A of the maximum value, M.. Recall our modified softmax normalization from Algorithm [given E IR::
2n 1
(x)
(e
(e
Notice that (x), > 0 only when 2; > O. Hence, we can see (a) as a probability vector over a which only has non-zero values corresponding those a; that within w((A) of MA. If take a (p=(a))² a, we observe that (pp=(a) (a)) a is a convex combination of the points in A.
Thus, given E Ω and gu Q, make the following important observations about ga.
16

---

Observation A.7. Given 92 qu Q the convex combination of subset of points Pr, .... For each such point Pl. (u, P1.) E [maxpep(u..) p) - sw,, (P), maxpep p\}.
Observation A.8. Given u E 22 (u, qu) E mmaxper(u, p) - Ew. (P), maxper p/}
Our goal is to show that for any E S the u-projection w W.(Q) (Q) is an e-approximation of the interval (u-projection) w a (P). First, note that by construction, each point Q convex combination of subset of points in P so Q S CH(P). This implies that w w.(Q) S (P))). What
remains show that (Q, 2 3E 3e) If 92 then this holds
max(u, q) mi, a) 2 (u, (u q-u) gEQ
gEQ per
max(u,p) EW)
min (u, (P) due Observation
pEr
W. W.(P) PP) (P)
(1 32) we)
Consider when u & Q and = Ava
_s
Then there w' E Ω such that ||u - w/ll S due to
construction of 52 and =u' Q. Then
Ww (Q) = max(u', (u', .) min(u',
gEQ
qEQ
2 (u', qw))
min(u', ,4)
sEQ
2 (u', argmaxperr p}) sw.)(P) min(u', .q) TEQ
(Observation 2)
(u', argmaaperrr (u', (u', p)) EP) max (-u',
DEQ
max(u', .) EW. (P) (-u', q-w") PEP
max(u', ,P) EW. (P) (1-u', argmaxpep (-u)) p)) ew (P))
PEP max(u' -min (u', 20w (P) -1 22 -2)) (P)
pEP pEP
By Lemma A.2
W. (..()) (Q) 2 ww (Q) 2AVd
(1 22) 22) (P)
2 (1 2$) (w), - 2Xvd) - 2AVd
(1 26 2e)w,( 2XV0(1 2$ +1)
(1 2: 2s),,(P) 4AVA(1
Therefore, by Lemma A.1
W. (Q)
4Xvd(1 =)
2e
W,, (P)
(P)
21-28 4Xvd(1 =)
due to a-fatness of P
21 28 c(1 -c)
21 38
and we get our desired result i.e. (Q) 2 (1 33) (P)
Proof of Theorem 3.4 Let k(E) 2 0 2013
and let ? be a fixed set of directions such
that [S2] = k(z). Notice that here, since A(E)
2 0
by Theorem 3.3 the output of
BE/S TVa
17

---

Algorithm
would be relaxed-s-kemel. Let Finner & Rk(c) such that
F Finner (S)
=
max ES (ux()), 2)
Additionally, let Fouter,1 Rd x R Rk(()) such
(x, un) (x, u2
Fouter, (x)
(x, uk(e))
and Fouter,2 RR(()) x Re(c) and y RR((s), let Fouter (2,, v) = F (Fouterr, + y).
+ Rk(e) be defined as 2 ReLUUx + y). Given Rd
First, we note that l -noms converge to the lo- noom so there is such that for any E RN, -
za Finner can be approximated within sa via sum-decomposition by first ||>||=|| < 2
s)²)T E (R((s) and then taking ( //p mapping each E S to (s) = [[u,, s)",... ()
where the 1/p-power is taken elementwise. Thus, by the universal approximation property of MLPs, there multilayer perceptrons MLP1 and MLP2 such that
)
Σ ELPP2(0) SES
F Finner (S) MLP,,
This means that F Finuer (5); is within for max.es(u;; s) for any S Xx. Because each set in Na is a-fat, Vu E 5d-1, Pinner(S is within ew,(S)) of the maximum value. In other words,
[MMPP LES
MLP1
Finner (S); SE.ase- Ww, Ww,
We can implement Fouter, 1 with MLP3 i.c. F Fouter, (x) Fouter, by choosing its weight matrix to be diagonal with entries [uI,..., (A(E)) along the diagonal. Similarly, Fouter;2 can be exactly represented by
MLP3(x) where MLP; can realize
Fouter, (2., y) = MLPa(x + +)
where MLP4 represents the identity function followed by a ReLU activation. Fouter can be rep- resented by neural network d such that (b( = ML.P (MLPP()))3(r) + y)) Given P E X, and
P. E
ReLU((u,,P)) + ew.. (P) maxpep(u1,p))
MLLP2(s) )) L
Pi MLP1
(eTTe( + ew.,, (P) max
This is exactly the point-wise update computed in a SumFormer architecture so if we instantiate SumFormer S. with the ML.Ps described above and each MLP in S. mapping dimension of k(s). Qs = (S. (P)) P is a relaxed-e-kermel by Theorem 3.3, Additionally, note that each MLP used to approximate Qs, maps to (*(()) where k is independent of the size of the input and only dependent the input dimension d, the fatness of the point set a, and the desired approximation error E.
intermediate
know that Q= Ta (S is relaxed Proof of Corollary 3.5 From Theorem 3.4
e-kernel for P. By Theorem 3.2 since Qe is a relaxed e-kernel, it is 3cs-coreset for P. Then (P(). (). By the universality of PeepSets,NNoogpeee
(1-3cz))u(P) ({(2) < (1+3ce))u(
approximate to arbitrary accuracy for any point set in &² Thus, there is Weeppet architecture such that
Walepset (Qc) p(Q=)l <
and we get the desired result.
18

---

A.3.2 Proofs from Section 4
Proof of Theorem
Note that the non non-relaxed version is also given in (2]. For completeness, we prove this theorem for the relaxed case which essentially just follows from the definitions of duality.
First for any point I E Id-11 let å = | 1] denote the point in Rd with the last coordinate being 1. Let ((x) == 2/ | dd be the unit vector in direction z. Let 8 be the positive semi-sphere. It is easy to see that ø is bijective from Rd to s Note that for any R (2, f*) and for any set of functions H,
Lx(x)= min h( (z) ||>||
min hx)
and
REH
kCH
Un(2)= = max h(z) =
||||||
max hEH
(1(x)) h*)
DEH
Then
(x) = | -ell-Wo(r)) We( (HL)
where H. is the dual point set of H.
If g = (g....., .k. is relaxed e-kernel for F. Then for any a Rd, we have that Lx(x) 2
[x) - (x)( and U=(x)= & Ux)x) + =x)()) It then follows that for any x E Rd-1,
min (6(z), f*) 2 min (o(x), eWo(s) (F*) and a E
rEF.
max (b(x), < max (ó(x), ()) + swooz) g Eg
That is, for any E s W (g e-approximates W (F*). Given that (-u, = - (u, p) for any point p. this means that w (g*) E-approximates (F*) holds for any u S U s Hence the only directions left are sd n {æ Rd = 0}. However, given that each term above is continuous, this holds due to continuity.
The other direction follows easily from the fact that being bijective.
Proof of Theorem 4.4
Suppose F admits linearization of dimension m. For any x E Rdd we will show first that & e, (z) S غ (z). Then we will show that & (x) 2 (1 - =))()))) If we use Algorithm| too compute a relaxed-e-kernel of the dual Jr, we know that each of E Q
q at (aa1)
+ a'v (aN)
where Σe= of = 1. Additionally, we will let 12:1.
Then we know there a ai E O where
(o((a)
(aia))
tim (a1) :
(:(x) (aj...aw)
+(a a'y
+1 +(a +aff...ay) a.y)
(m(())
vo(aN))
v2(aa))
(mn()N))
To ease notation, for any j {o. and i E [k], we write
1 ((1(
ERN a'= R
(aN))
so (z) = (a + ( 18p1 1))()))))))))))))))))))))))))))) + ...
We can re-write qi as convex
combination of elements in F:
(x) = a (a1) [x))) + ... (aN)
= f + .... a'y (x(x)
Let w E IRd and let f argmin (x). Then for any d: E,
(x)x) = a//1(x) + (. /N((2) of ... aax (x)
Therefore, To = mingeg, (xx) 2 [x(x)) = minjer f(x). similar argument shows that Uo. (x) < Uz(x).
19

---

Table Dataset details for approximating relaxed-e-kernels. Peraiul and |Pest refer the size of the train and test point clouds, respectively. The first four columns describe synthetic datasets while the last two columns describe two real datasets. For the 'Uniform ball' dataset, we sample point clouds uniformly from a d-dimensional ball. Note that for the Uniffrmm ball' and 'Uniform Ellipse' in R:10, we use point clouds size 700 to train and test. For 'Uniform Ball', we will sometimes call it 'Uniform Disk' for point clouds in I2 For 'Ellipse', rotated point cloud. For 'Single Gaussians', we sample point clouds from a Gaussian with a random standard deviation and 'Gaussian Mixture' refers to point clouds sampled from two to five randomly placed Gaussian clusters. Note that for ModelNet, we apply random scaling to the point cloud so that the bounds are between [-5, 5]. See 43 and 26 for more details regarding SQUID and ModelNet, respectively.
sample from randomly scaled and
Synthetic
Real
Uniform Ball
Single Gaussian
Gaussian Mixture
Ellipse
ModelNet
SQUID
PPersill Ptest
500, 700 (for I 10) 500, 700 (for (0)
500, 700 (for I R!
500
500
200
350
500, 700 (for !0)
500
500
200
350
# train point clouds # test point clouds
3000
3000
3000
3000
2048
774
750
750
750
750
2048
332
Input dim.
2,3,5,10
2,3,5,10
2,3,5
2,3,5
3
2
Bounds
[]5,5]
[-5,5]
[-5, 5]
[-5,5]
[-5.5]
[0, 450]
Now we will show that &g. (x) (1 e){x(z) for any x E Rd. Given x E Rd, we know that (xx) = (1,)) ................................ pm (xr) E Rm++1 Define Jriin and Q to be a set of linear functions
JLin
pLin [1) ( [m)] = ((a))²
: aj A
Q (..)))
i [m]]
3m
First, notice that (FLimy F and (Q!in)= O We know that O is relaxed-s-kereel of F so by Theorem 4.3 Q. is relaxed-e-kerel for F Given any x E Rd, we know that fi(z) = = f! (z)) so
Ex(x) = (1)x)).
Similarly, we know that 03 (x:) = gl
Eg (x) Egiial (g (f(x)).
Since Q..in is relaxed-e-kemell for F+
Eo. (x) 2 - ()))
A.4 Additional experimental details and results
All models are implemented in Pycoorch and trained on 8 NVIDIA RTX A6000 GPUs. Our code is
publically available Additionally, all models are trained using the ADAM optimizer 20) provided in PyTorch and trained using learning rate of 0.001. Relaxed-s-kernel networks trained for 200 epochs while all extent-measure models are trained for 500 epochs. Additionally, for the processor for
20

---

Table 4: Dataset details for extent measure approximation tasks. |Persin| and |Peest| refer to the size of the train and test point clouds, respectively. The 'Uniform Ball' dataset is used for the minimum enclosing ball task and consists of point clouds randomly sampled from a d-dimensional ball. The 'Uniform Elliisee dataset is used for the minimum enclosing ellipse task and consists of point clouds sampled from randomly scaled and rotated ellipses. The 'Uniform Annulus' dataset is used for the minimum enclosing annulus task and consists of point clouds sampled from annuli with widths from 0.1 to respectively.
See (43] and 26 for more details regarding SQUID and ModelNet,
Synthetic
Real
Uniform Ball
Uniform Ellipse
Uniform
ModelNet
SQUID
Annulus
Perain
200
100
100
200
350
PLest train
200
100
100
200
350
3000
3000
3000
2048
774
point clouds
# test point clouds
3000
3000
3000
2048
332
Input dim. Bounds
2,
2
2
3
2
[-5,5]
[-5,5]
[-5,5] 5]
5,
[0, 450]
the encode-decode process models (used for extent measure tasks), we fix the processor to take input from R$, have three blocks (either SumFormer or Transformer) and output 150 points from No.. We choose this configuration as these hyperparameters had the best performance the relaxed-e-coreset task in R.. Additionally, for the frozen training regime, the processor networks (N₂,) take input of point cloud P in R (which could contain arbitrary number of points), output k = 150 points, and are pre-trained on the 'Mixed Synthetic' data in R Detailed dataset specifications for the relaxed-e-kenne experiments are given in Table and those for extent-measure tasks are given Table 4 All code (including models, hyperparameter settings, and synthetic dataset generation) is available.
Size generalization for extent measures. Here described the train and test set details for the size generalization experiments on the extent measure tasks described in Section [5] Figurel6jar well in our motivating example in Section 2 Each model used for our size generalization experiment is trained on the synthetic RR2 datasets detailed in Table For the minimum enclosing ball (MEB) task, test point clouds have sizes N 500, 1000, ..... 17000, with the bounding box from which test points are sampled defined as [ N//500 N/50002. For the minimum enclosing ellipse (MEE) and minimum enclosing annulus (MEA) tasks, test point clouds have sizes N 100, 200, .... 3000, and the bounding box scales as | 1/100, 2/100
Hyperparameter details. For our hyperparameter search on the relaxed-g-kernel, we chose the depth of the network from (2, 3, 4). the hidden dimension from {128, 256, 512, 1024), and the embedding dimension from 16, 32. All results in our paper are reported on the best performing models from our hyperparameter search. For the extent-measure models, we fix the hyperparameters of the processor based on the best configuration from the s-kernel task and search over the hyperparameters (width/depth) of the encoder and decoder networks. The depth of both the encoder and decoder MLPs are sampled from {2, 3, 4} and the width from {64, 128, 256}. Finally, we also tune the number of epochs trained and chose to test the models trained for 200 epochs as they had the best validation loss. We note that we did not observe the transformer OOD performance to improve with longer training times.
Loss functions.
Here, we list all loss functions used to train each task given input point set P.
Relaxed-g-kernel: To train model to approximate relaxed-e-kernel, each epoch i, we first sample a random set of 100 directions 24, We then compute the difference between the max projection of P and No. (P) for d E Q2 well as the difference between the min
21

---

projection of and No. (P) for d E Dj:
1 Lg (P, (P), D.) = Del
Σ aelt
mmax(u,)) PEP
max (u, 4)1 + minnu, GENo, (P)
(u.p) PEP
min geNs (P)
(u, 2)1
Minimum enclosing ball: We aim to approximate the radius of the minimum enclosing ball. In order validate that we have actually learned the ball, also predict the center of ball. Therefore, given an input point set in R we configure Wextent such that That.Wes Wextent (P) E RR++1 where the first d coordinates, Nexteent Nextteni I represents the radius. Given the ground truth center Rd and radius r E IR, the loss function we use to train Nextent is
represent the center and the last coordinate
[(c, Nextent (P)) = |cc Nexeeen (P).:al ((r--Nextent (P)
Minimum enclosing ellipse: Recall that we aim to predict the minimum area enclosing First, we note that we center all data the origin for the minimum enclosing ellipse. Unlike the minimum enclosing ball, we do not predict the center for the ellipse. Given an input point P C R& configure Nexetent such that Nextent (P) E R where Nextent (P)1 represents the major radius. Nextens (P)2 represents the minor radius, and Nextent (P)s represents the angle of rotation. Given the ground truth major radius Tmaj E R. minor radius Tmin E R and angle of rotation @ E R, the loss function we use to train Nextent
ellipse.
is
[([majj minn: 0.Nextent (P)) = (Tmai Noxtent (P))) + (Tmin -Noxtent (P)2)² (sin(0) sin(Neextent (P)s))² + (cos(0) coseteettet (P))))
Minimum enclosing annulus: We aim to predict the minimum width of the minimum enclosing annulus, which can be computed by predicting the inner and outer radii of the annulus and then taking their difference. Given an input point set P C Rd 18d,Nextent (ex)eet(P) E R² where Nexteut (P)a+1 represents the inner radius and Wexteett (P) P))+2 represents the outer radius. Then given the ground truth inner radius Finner E R and outer radius Touter E R, the loss function we use train Nextent is
((c, Tinuer, Touter; Niaeer:Neeeee Nextent (P)) = |rinner NNxxtent (P)1 +
| -Nxxtent (P)2l
Tinner
Touter
A.4.1 Additional experiments for approximating relaxed-s-kennlls
First, we note that we include all complete tables from the main text with error bars in Table and Table 6 We additionally include results on datasets in higher-dimensional synthetic datasets R in Table 7 and IR ' in Table g We see largely the same trends, where the S. performs comparably to Te on in-distribution data and then S, performs much better than Te on out of distribution data, Although the classical e-kernel algorithm sometimes has lower directional error than S,, we compare the runtime of the e-kernel algorithm with all neural approaches in Figure 1T and show that our neural models are generally much more efficient at inference time than algorithmic approaches. We also provide more extensive results in Tables 9 10 and [I] where we detail the performance each neural approach different types of synthetic and real datasets.
For the relaxed-e-kennn tasks, we also provide several sensitivity analyses showing the effect of input dimension, fatness of point sets, and the size of relaxed-e-kente on the direction error (Edie). For each of these sensitivity analyses, we also provide a baseline comparison to the fluxed-s-kerne algorithm described in Algorithm given network with respect to its aligned algorithm. In all cases, the data-driven way of learning the relaxed-e-kent presents significantly more accurate (in terms of directional error) coresets than the baseline algorithmic implementation.
0.1 in order to analyze the behavior of the neural
we know that the accuracy of the approximation of the relaxed-e-kerel will depend on the dimension of the input point cloud. We verify this empirically in Figure across different sizes of e-kernels. For this experiment, we train and test each model on the point clouds with 500 points sampled uniformly from a ball R where / 3,5. We can see in Figure 7 that Edit increases the input dimension of the point cloud increases.
Effect of input dimension. From Theorem 3.4
22

---

Effect of c--fatness Similar to the relationship between enror and input point cloud dimension, we know from Theorem [.44 that the accuracy of the approximation of the relaxed-s-kernel will depend on the o-fatness of the input point set. To verify this, we train both the SumFormer and Transformer model on point clouds with 500 points sampled uniformly from balls in TR& and RR² (disks in the case of )R.2) We then test on point clouds of 100 points sampled from ellipsoids which have their minor axes scaled to simulate point clouds with a range of a-fatness. The results are reported in Figure 8 Indeed, we see that as increases (i.e. the point cloud becomes fatter) the accuracy of our approach increases.
Effect of output size. In order to examine the effect of the output relaxed-s-kermel size for the quality of the approximation, we plot the normalized oulput size (i.c. number of relaxed-s-kernel points/total number of input points) against the directional width error. See Figure 9 As expected, we see that the error decreases as the output size increases.
capabilities of the models in terms of generalizing to larger point sets. For this experiment, we train each model on the point clouds with 500 points sampled uniformly from a ball in R where D {2, 3, 5] and then test the models on much larger point clouds (up to 1000 points per cloud) sampled from the uniform ball. The results reported in Figure and we find that the SumFormer model generalizes especially well to out-of -i-iiitribttionn point set sizes (maintains low error
Effect of input point set size. We also examine the
A.4.2 Additional experiments for approximation of extent measures
We include the full results from the main text (which include the percentage of points excluded from each covering object). The full results each extent measure task are included in Tables [2] [3]
14 and 15 for minimum enclosing ball in R², minimum enclosing ball in R$, minimum enclosing ellipse in 22 and minimum enclosing annulus I2, respectively. We also include comparisons to classical algorithmic approximations in our full experimental tables. In particular, we evaluate the standard pipeline of first computing an E- e-kernel and then applying the exact algorithm to the resulting coreset, For MEB and MEE, we use Welzl's 's algorithm as the exact solver; for MEA, we use the quadratic programming formulation implemented in the Computational Geometry Algorithms Library (CGAL) 35). Additionally, Figure reports the inference times of the neural models alongside the runtimes of the corresponding algorithmic approaches.
First, note that our Akernel-aligned model, the frozen Sextent, misses much smaller proportion of points than other models (even those with lower radius or width prediction error) indicating that its predicted shape more accurately captures the true enclosing object. Notice that while classical algorithms can achieve higher accuracy in some cases, our neural models outperform them on the minimum enclosing annulus task, which is more challenging than the other extent measure tasks as it is unfaithful and non LP-type. Moreover, as shown in Figure 12, our neural approaches are substantially faster than all algorithmic baselines (both the exact and the approximation), particularly for the minimum enclosing annulus. Finally, as emphasized in the main text, neural approximations offer a key conceptual advantage over classical algorithms beyond gains in speed: they do not require explicit knowledge of the underlying optimization objective. To train our neural models, only labeled data and the knowledge that the problem belongs to the general family of extent-measure measure tasks are needed. In contrast, classical algorithmic methods require full specification of the objective and often the design of custom algorithm to solve each specific problem.
Finally, Figure 13 presents additional results for the size-generalization experiment shown in Figure 6 where we record the proportion of points excluded as the number of points per cloud increases. Not only does the frozen Sextent model outperform all other neural baselines in terms of size generalization and the error (as seen in Figure 6 but also the predicted output from the frozen Sextent model misses a low proportion of points. Notably, models that exclude fewer points than the frozen Sextent tend to exhibit higher width or radius error, indicating an overestimate of the enclosing object. This can also be seen in visualizations of the predicted output from each model in Figure 14, where we see that the frozen Sextent model can better adapt to out-of-distribution input data.
23

---

A.5 Figures and Tables
Table Edir on datasets in TR22 for output relaxed-c-kernel of 16 points. We compare Sumformer and Transformer neural approaches across three different test sets for each train set. Note that 'Mixed Synthetic' has no 'OOD, Synthetic' because the train set contains all types of synthetic data. Boldface indicates the lower enror per row.
Test Sets
OOD
Train Set
Method
In-dist.
Synthetic
SQUID
S
0.060 0.026
0.044 0.042
0.127 0.111
T
0.029 1 0.013
0.098 1 0.056
0.275 0.112
Ellipsc
S.
0.131 1 0.029
0.354 1 0.172
0.993 1 0.002
T,B
0.117 1 0.045
0.63 1 0.115
0.976 1 0.007
S:
0.014 1 0.013
0.043 1 0.040
0.028 1 0.043
T
0.027 1 0.024
0.097 1 0.049
0.218 1 0.101
Gaussian Mixture
S..B
0.146 1 0.062
0.146 1 0.057
0.962 1 0.011
T,B
0.19 0.087
0.383 0.067
0,94 0.015
S.
0.028 = 0.022
0.114
0.028 = 0.022
T
0.061 = 0.052
+ 7.137 3.892
0.40 0.109
0,061 = 0.052
SQUID
S.
0.421 = 0.511
0.421 0.511
T
0.228 = 0.207
14.561 6.632
0.228 + 0.207
S.
0.027 1 0.018
0.065 1 0.071
Te
0.032 1 0.024
0.296 1 0.113
Mixed Synthetic
Sc,B
0.094 = 0.058
0.971 = 0.008
Te.B
0.203 = 0.181
0.939 = 0.017
Algorithmic
B..R
0.180 + 0.079
0,228 0.139
Baselines
B..E
0.040 - 0.049
0,062 = 0.095
24

---

Table 6: Edir for predicted relaxed-e-kernels of 64 points R We compare Sumformer and Transformer neural approaches across three different test for each train Note that 'Mixed Synthetic' has no "OOD, Synthetic' because the train set contains all types of synthetic data. Boldface indicates the lower error per row.
Test Sets
OOD
Train Set
Method
In-Dist.
Synthetic
ModelNet
Sc
0.049 + 0.019
0.032 + 0.024
0.066 + 0.053
T.
0.055 + 0.021
0.106 + 0.076
0. + 0.077
Ellipse
S.
0.221 = 0.039
0.462 + 0.098
4.736 3.49
T,B
0.243 = 0.056
0.555 + 0.063
3.603 = 5.454
S
0.047 0.027
0.039 = 0.026
0.064 = 0.050
Te
0.054 = 0.027
0.066 + 0.033
0.250 = 0.125
Gaussian Mixture
Se,n
0.274 + 0.049
0.289 + 0.029
1.949 + 3.49
T.B
0.357 + 0.146
0.851 0.104
4,486 + 5.514
S:
0.041 + 0.037
+
0.041 + 0.037
T:
0.049 + 0.044
0.265 + 0.1118
0.049 + 0.044
ModelNet
S.B
0.378 0.621
0.542 + 0.069
0.379 = 0.621
T.
0,542 = 0.952
0.658 + 0.142
0.542 = 0.952
S
0.035 = 0.029
0.055 = 0.048
Te
0.042 + 0.038
0.1 + 0.071
Mixed Synthetic
Sen
0.174 + 0.054
1.518 + 2,288
Te,
0.289 = 0.179
4.356 = 5.257
Algorithmic
Bann
1.016 + 9.988
2.176 + 2.849
Baselines
B.
0.062 + 0.040
0.050 + 0.047
Table 7: Edit for predicted relaxed-e-kernels of 200 points in R We compare Sumformer and Transformer neural approaches for in-distribution and outtt--distionttion synthetic test sets. Note that there are no real datasets in IR so the only test sets here are synthetic.
Train Set
Method
In-Distribution
OOD, Synthetic
S
0.084 + 0.016
0.091 0.041
Uniform Ball
Te
0.118 0.022
0.29 + 0.117
S.
0.238
0.694=0.0
T.B
0.35 0.043
0.575 0.249
S
0.085 0.02
0.077 0.027
Ellipse
T
0.084 + 0.024
0.196 + 0.133
S
0.399 + 0.108
0.589 + 0.256
T
0.343 + 0.096
0.614 0.167
S
0.065 + 0.018
0.10 + 0.033
Single Gaussian
Te
0.065 + 0.022
0.183 0.053
Sg
0.352 + 0.048
3.75 3.75 0.154
T
0.333 + 0.044
3.941 0.112
S
0.084 + 0.028
0.087 = 0.027
Gaussian Mixture
Te
0.091 + 0.025
0.109 + 0.032
Se
0.717 + 0.021
0.465 + 0.184
T
0.757 + 0.278
1.488 1 0.344
Sz
0.075 + 0.025
Mixed Synthetic
Te
0.087 + 0.032
Sc,n
0.347 + 0.188
Te.B
0.879 + 0.599
Algorithmic Baselines
Be
0.653 0.366
B
0.083 + 0.033
25

---

Table 8: Edit for predicted relaxed-s-kernels of 200 points in R20, We compare Sumformer and Transformer neural approaches for in-distribution and out-of-distribution synthetic test sets. Note that there are real datasets in IR so the only test sets here are synthetic.
Train Set
Method
In-Distribution
OOD, Synthetic
0.367 + 0.0289
0.301 + 0.074
Te
0.259 + 0.0227
0.292 + 0.044
Uniform Ball
S.
0.290 = 0.033
0.459 0.214
T.B
0.266 + 0.029
0.435 + 0.208
Se
0.222 = 0.037
0.275 0.062
Te
0.251 + 0.042
0.276 + 0.041
Ellipse
Sc,
0.693 + 0.166
0.518 0.209
T
0.777 + 0.192
0.582 + 0.281
S.
0.241 + 0.036
0.258 + 0.034
Mixed Synthetic
Sc.B
0.530 + 0.281
Te,B
0,535 + 0.287
Algorithmic Baselines
Be,R
0.621 + 0.225
B2,E
0.199 0.034
26

---

Table Directional error across 2D datasets for various e-kernel sizes. Note that we already report performance for the mixed synthetic data in the tables in the main text so we do not report the performance here.
Train
Method
Uniform Disk
Ellipse
Single Gaussian
Gaussian Mixture
SQUID
S.
0,040 1: 0.013
0.109 1 0.081
0.125 1 0.057
0.074 1: 0.039
0.101 E 0,065
T:
0.040 1: 0.013
0.200 0.094
0.370 1: 0.078
0.346 0.144
0.297 1: 0.110
16
SL.B
0.237 +: 0.009
0.544
0.159
0.767 0.017
0.712 + 0.115
0.995 0.002
Tr.8
0.061 + 0.007
0.456 + 0.167
0.720 = 0.019
0,512 0.159
0.973 = 0.008
Uniform
S.
0.008 1: 0.004
0.065 0.051
0.214 1: 0.057
0.061 0.061 0.053
0.264 + 0.093
T:
0.007 4 0.004
0,158 0.079
0.385 0.058
0.287 0.123
0.236 0.099
Disk
S..
0.062 + 0.008
0.443 + 0.165
0.703 + 0.020
0,561 0.123
0.975 + 0.007
Tr
0.044 + 0.011
0.456 0.186
0.702 0.020
0.534 0.134
0.972 0.009
S.
0.006 + 0.003
0,069 0.057
0.128 = 0.062
0.097
0.174 + 0.085
200
T.
0.005 + 0.003
0.199 0.110
0.463 0.041
0.112
0,427 = 0.109
S..B
0.111 + 0.008
0.473 0.
0,721 0001
0.589 0.103
0,982 0.005
Tr.8
0.123 + 0.010
0.484 + 0.167
0.739 + 0.018
0.599 0.144
0.975 + 0.008
S
0.045 + 0.013
0.058 0.026
0.042 0.039
0.007
0.130 0.109
Tr
0,031 + 0.010
0.029 0.013
0.093 = 0.056
0.050 0.041
0.272 + 0.108
S,,
0.110 + 0.012
0.131 0.029
0.458 = 0.039
0.495 0.271
0,993 + 0.002
T.,8
0.715 1: 0.061
0,119 0.046
0.601 0.035
0.575 0.247
0.975 0.007
S.
0.011 1: 0.005
0.015 1 0.008
0.034 1: 0.050
0.078 1 0.086
0.088 1 0.070
Ellipse
64
T.
0.013 + 0.005
0.012 0.006
0.116 = 0.057
0.033 0.032
0,211 = 0.087
S,
0,121 1 0.010
0,146 0.029
0.438 + 0.039
0.456 0.210
0.976 + 0.007
T.,
0.674 + 0.049
0,101 0.040
0.613 0.031
0.593 0.231
0.978 0.007
0.004 1: 0.002
0.003
0.033 0.046
0.057 0.077
0.118 0.073
T:
0.010 + 0.004
0.008 0.005
0.030 + 0.027
0.034 + 0.033
0.197 + 0.079
200
S,
0.098 + 0.011
0,118
0.025
0,445 = 0.038
0.435 0.215
0,989 = 0.003
g
0.217 + 0.028
0.076 0.030
0.436 0.038
0.583 0.413
0.961 0.011
S,
0.056 1 0.015
0.097 1 0.052
0.032 1 0.020
0.071 1 0.049
0.091 = 0.069
16
T.
0.062 0.017
0.029
0.019 0.014
0.080
0.206 0.095
S..B
0.924 + 0.031
1.174 0.604
0 + 0.030
1.256 + 0.638
0.946 + 0.015
Gaussion
Tr.8
2 + 0.109
2.376 1.023
0,246 0.053
2.200 = 1.126
0.922 = 0.024
0.029 + 0.009
0,050 0.029
0,011 0.010
0.039 = 0.032
0.078 0.068
T
0.052 + 0.015
0,056 + 0.027
0,005 = 0.007
0.083 1: 0.058
0,211 = 0,100
S,,8
0,884 + 0.032
1.102 0.612
0,101 + 0.032
1.314 0.741
0,949 0.015
T..8
2.374 + 0.102
2.209 0,941
0,152 0.044
2.147 = 1.089
0.879 = 0.028
200
S.
0.017 + 0.007
0.057 + 0.060
0.003 = 0.001
0.056 0.048
0.067 = 0.058
0.047 0.015
0.020
0,004
0.071 0.049
0,220 0.099
SeM
0.927 1: 0.031
1,131 1 0.617
0,114 1 0.030
1,16 0.703
0.944 1 0.019
8
2.456 0.125
2,151 0.946
0.041
2.216
0.024
S.
0,024 1 0.008
0,033 1 0.015
0.071 0.059
0.025 E 0.037
16
Tr
0.040 + 0.011
0.031 + 0.011
0.063 = 0.050
1.022
0,214 0.100
S.,
0.067 1: 0.010
0,087 0.025
0.188
0.128 0.058
0.967 0.011
T.u
0.686 4.0.051
0,485 +0.075
0,272 +-0.447
0,190 10.086
0.944 +-0.015
Gaussian Mixture
S,
0.015 1 0.006
0.018
0.010
0.107 1: 0.067
0.006 1 0.006
0.015 1 0.013
64
0.032 4 0.011
0.017
0.008
0.026 0.033
0.009 0.010
0.156 + 0.082
S.M
0.062 + 0.010
0.084 + 0.024
0.179 + 0.046
0.121 + 0.052
0.963 + 0.011
T.B
1,031 +0.050
+0.105
0.316 +0.046
0.164 +0.075
0,947 +-0.115
8.
0.005 1: 0.003
0.009 0.007
0.100 1: 0.047
0.003 0.004
0.012 1: 0.018
200
T.
0.030 + 0.012
0.011 0.006
0.032 + 0.033
0.006 0.007
0.149 + 0.084
S.,
0.086 + 0.010
0,103 0.026
0.193 0.046
0.138 0.067
0.966 0.011
T
1.706 4:0.822
0,815 10.140
0,356 10.052
0.191 103
0.940 +0.014
S.
0.5.88 + 0.012
0.328 0.027
0.517 = 0.010
0.3680.183
0.029 = 0.021
16
T.
0.431 + 0.011
0.303 0.060
0.390 = 0.081
0.368 = 0.13
0.066 + 0.051
SQUID
S..
0,191 10.061
9,954 3.629
2,875 + 0.296
10.191 + 4.073
0.283 + 0.276
T.
19,858 20.815
18.238 26.512
5,490 10.519
16.164 16.000
0.231 #0.221
S.
0.287 + 0.014
0.289 0.032
0.411 + 0.017
1214
0.009 + 0.008
64
T.
0.373 + 0.025
0.376 0.039
0.409 1 0.057
0.350
0.062 + 0.042
S.M
0.499 16.621
16.123 = 4,591
6.463 0.608
12.393 5.642
0.224 1 0.202
T
22.050 11000
19.865 = 7.018
5,916 10.611
16.114
0.234 +0.211
S.
0.368 + 0.013
0.339 0.031
0.378 = 0.048
0
0.009 + 0.009
200
T
0.322 1 0.059
0.346
0.069
0.463 = 0.081
0.379 2 0.140
0.047 + 0.036
S..
5.683 1. 0.144
2.142 5.374
1.582 1: 0.179
6.337 4.633
0.199 1 0.199
T.9
15.879 +-0.788
15.438 +4.420
4,426 +0.48T
13,109 +-5.951
0.261 +0.243
S.
0.038 1 0.012
0.052 1 0.024
0.019 1 0.015
0.031 1: 0.026
0.064 1 0.073
T.
0.035 + 0.011
0.046 0.023
0.017 0.014
0.040 0.033
0.307 0.112
Mixed
S,
0.046 1: 0.008
0.057
0.016
0.069 1 0.017
0.124 1: 0.058
0.971 +: 0.008
T.
0.577 + 0.0509
0.646 0.267
0.220 0.059
0.512 0.329
0.939 + 0.017
0.010 1. 0.004
0.008
0.023 0.030
64
T:
0.016 +- 0.007
0.014 + 0.006
0.001 + 0.003
0.014 + 0.017
0.183 + 0.080
S.B
0,109 + 0.010
0.136 0.031
0.108 + 0.029
0.138 0.065
0.967 0.010
T..
1,339 1 0.094
0.877 0.265
0,320 = 0.073
0.561 0.368
0.922 + 0.024
S.
0.006 1. 0.003
0.008 0.005
0.001 1: 0.002
0.006 1 0.006
0.014 :: 0.022
200
To
0.014 + 0.008
0.012 0.008
0.001 0.003
0.013 0.004
0.144 0.062
S..
0.251
+ 0.012
0.285
0.121
0,261 = 0.049
0,391 # 0.222
0.949 + 0.015
Tz.
1.428 1 0.064
1.133 0.366
0.238 1 0.055
0.468 0.289
0.913 - 0.024
27

---

Table 10: Edit across all 3D datasets for various e-kernel sizes. Note that we already report performance for the mixed synthetic data in the tables in the main text so we not report the performance here.
Dataset
Architecture
Uniform Ball
Ellipse
Single Gaussian
Gaussian Mixture
ModelNet
S.
0.180 1 0.030
0.239 1 0.069
0.159 0,045
0.180 0.072
0.161 0.094
16
T,
0.180 = 0.032
0.358 + 0.085
0.553 = 0.030
0,421 0,123
0,426 0.133
Uniform Ball
S_.8
0.251 + 0.031
0.620 + 0.214
0.774
0.643 0.128
2.887 +
T.,
0.149 = 0.019
0.569 = 0.2
0.757 = 0.015
0.623 0.133
3.547 5.67
0,046 = 0.012
0,051 + 0.018
0.029 = 0.014
0,050 = 0.028
0.067 0.057
64
0,041 + 0.010
0.198 + 0.079
0.389 0.047
0,257 0.093
0,361 0.111
S,.
0.161 + 0.018
0.582 + 0.204
0.759 0.015
0.673 0.086
5,920 + 7,937
T..
0.149 + 0.019
0,569 0.2
0.757 0.015
0.623 + 0,133
3.547 + 5.67
200
0,021 = 0.007
0,020 + 0.008
0.007 0.007
0.029 = 0,021
0,053 0.047
T;
0.014 = 0.008
0.158 + 0.065
0.332 = 0.055
0.237 + 0.097
0,361 + 0.111
S,,
0.152 + 0.019
0.572 0.203
0.755
0.080
7,866
T.B
0,103 1 0.017
0.543 1 0.195
0.746 0.016
0.603 0.141
2.817 3.886
16
S
0.178 0.029
0.074
0.159 0.045
0.187 0.076
0.149 0.093
T:
0,176 1 0.027
0.244 1 0.078
0.235 0.063
0,235 0.111
0,232 0.114
Ellipse
n
0.188 + 0.014
0.221
0.036
0.562 0,027
0,191
3.180 3.799
T,,0
0,257 1 0.041
0.232 1. 0.048
0.600 0.035
0.898 0.466
3,276 4.107
0.043 0.010
0.049
0.019
64
T:
0.047 + 0.011
0.050 + 0.018
0. 196 0.068
0.075 0.051
0.163 + 0.089
S,a 8
0.187 0.014
0.221
0.039
3,510 4.736
7.n
0.425 + 0.046
0.243 + 0.055
0.625 = 0.027
0.615 - 0.117
3.603 + 5.454
0.021 0.007
0.021
0.009
0.007
0.049
200
T:
0,019 1 0.006
0.019 1 0.009
0.039 0.050
0.087 0.074
0,250 0.121
0.177 0.022
0.058
4.900
T.B
0,198 + 0.042
0.219 + 0.070
0,512 = 0.032
0,907 = 0.523
3.609 + 5. 109
0.180 0.03U
0.076
16
0,239 + 0.037
0.232 + 0.051
0.146 = 0.040
0.227 = 0.082
0,363 + 0.121
Single Gaussian
1,85 0.068
2.332 + 0.891
0.248 + 0.04
2.314 0.78
7,204 + 8.48
T.B
2.742 + 0.080
3,300 + 1.244
0,252 = 0.044
3,480 = 1.063
20.436 + 24.422
0.057 + 0.013
0,080 + 0.034
0.033 0.016
0.063 0.032
0.075 0.052
64
T
0,078 + 0.016
0.110 + 0.044
0.037 = 0.015
0,123 0.054
0.257 + 0.124
2,883 0.092
3.565 1.341
0.29 0.048
2.6
9.911 + .24
T.B
2.762 + 0.083
3.249 + 1.199
0.261 0.041
3.179 0.951
15,886 17.536
200
0.034
0.039 + 0.017
0.013 0.010
0,059 0.047
T:
0.069 + 0.016
0.075 + 0.026
0.014 = 0.010
0.088 + 0.044
0.219 + 0.100
1.179 + 0.052
1,791 + 0.716
0.17 0.032
2.17 + 0.712
10.473 14.457
T,a
2,707 1 0.079
3,286 1 1.236
0.263 0.042
2.997 0.903
16.368 19.089
0,131 + 0.031
0.231 + 0.062
0,163 0.046
0.179 + 0.072
0,154 + 0.092
16
T:
0,176 1 0.027
0,204 1 0.047
0.176 0.049
0.178 0.069
0.209 0.099
S.n
0,215 + 0.015
0.2145 0,039
0,292 0,041
0,259 0,069
1,800 2.784
T.B
2.175 + 0.103
1,408 + 0.223
0.392 = 0.049
0.425 0.179
5.125 6.100
Gaussian Mixture
0.054 1 0.013
0.061 1 0.020
0.032 0.019
0.047 0.027
0,065 0.053
64
T,
0,060 + 0.013
0.059 + 0.016
0.054 0.027
0.054 0.027
0,250 0.127
S,
0,261 1 0.015
0.266
0.036
0,343 0.035
0,274 0.049
1,941 3.493
T.n
1,222 + 0.065
0.952 : 0.198
0.378 = 0.048
0.357 = 0.146
4,485 + 5.514
0.027 + 0.008
0.030 + 0.013
0.010 0.009
0.023 0.014
0.042 0.037
200
T:
0,032 1 0.010
0.029 1 0.012
0.021 0.019
0.030 0.019
0.232 0.098
S.n
0.179 = 0.015
0.215 + 0.047
0.276 0.040
0,284 0,100
2,111 3,048
T.B
1,550 + 0. 0.086
1.220 + 0.212
0.352 0.045
0.416
4,501 7.400
S.
0.209 : 0.035
0.268 + 0.075
0.199 0.058
0,206 = 0.082
0,149 0.098
T,
0,448 + 0.029
0 + 0.073
0.683 0.053
0
0.150 0.096
ModelNet
S_8
0.255 + 0.017
0.384 + 0.088
0.660 0.023
0.627 + 0.124
0,363 0.538
T,B
0.589 0.048
0.373
0.019
64
S,
T.
0,303 0.027
0.113 + 0.022
0.217
0.148 + 0.043
0.051
0.182 0.052
0, 0.084
0.041 + 0.038
0.040
S.a
0.322 + 0.019
0.434 + 0.093
0.693 0.023
0.65 + 0.127
0,379 1.459
T.B8
0.593 0.058
0.703 0.229
200
S.
0.037 = 0.015
0.047 + 0.029
0.021 0.015
0.043 0.033
0.024 0.030
T
0.169 + 0.022
0,183 + 0.040
0.466 0.046
0,286 0,105
0.030 0.025
8_8
0,388 + 0.021
0.451 + 0.062
0.701 0.024
0.608 0,118
0.379 0.988
n
0.494 0.047
0.708 0.312
0.019
0.668
0.512 0.833
16
8
0.179 + 0.0.0
0.238 1 0.069
0.157 : 0.023
0.180 : 0.075
0,150 1 0.091
0.189 0.031
0.245 0.071
S.n
0.157 + 0.017
0.259 + 0.089
0.207 = 0.029
0.345 1 0.135
1.611 + 2.038
Mixed
T.
0,416 + 0.050
0.521 + 081
0.217 0.037
0.477 0.224
5,060 18.203
S,
0.040 1 0.010
0.047 1 0.019
0.020 1 0.012
0.042 1: 0.025
0.055 1. 0.049
64
0.044 + 0.010
0.055 0.024
0.068
S..
0.148 + 0.013
0.183 + 0.062
0.16 = 0.024
0.278 0.102
1,518 + 2.288
T.n
0,593 + 0.058
0.703 0.229
0.235
5.257
S,
0.017 = 0.006
0.017 + 0.009
0.004 = 0.005
0.022 = 0.016
0.032 + 0.032
200
0.023 0.007
0,023 0.012
S..
0.154 + 0.012
0.178 + 0.035
0.159 = 0.023
0.244 2 0.067
1,631 + 2.385
T..B
0.625 + 0.082
0.726 + 0.219
0,216 0.037
0.451 0.212
5.681 7.941
28

---

Table 11: Ear across all 5D datasets for various e-kernel sizes. Note that we already report perfor- mance for the mixed synthetic data in the tables in the main text so we do not report the performance here. Train dataset
Method
Uniform Ball
Ellipse
Single Gaussian
Gaussian Mixture
S.
0,431 = 0.043
0.562 + 0,086
0,426 1: 0.067
0.524 +: 0.102
T
0.464 = 0.048
0.514 + 0.069
0.676 1 0.038
0.599 + 0.092
S
0.440 = 0.047
0.742 + 0.248
0,803 + 0.012
0.725 + 0.111
Tr,n
0.352 = 0.044
0.684 + 0.202
0.816 + 0.011
0.741 + 0.099
S.
0.188 = 0.025
0.247 0.057
0.159 + 0.033
0.232 + 0.058
Uniform
64
T.
0.197 + 0.027
0.366 0.066
0.538 + 0.033
0.362 0.092
Ball
0.242 + 0.027
0.621 0.177
0.79 + 0.011
0.695 0.133
Te,
0.248 = 0.033
0.633 0.199
0.791 + 0.011
0.702 + 0.113
S.
0.084 = 0.016
0.112 + 0.038
0.058 + 0.023
0.103 + 0.038
200
T
0.118 + 0.023
0.202 + 0.052
0.369 + 0.047
0.356 + 0.111 0.113
S..B
0.238 + 0.03
0.63 + 0.198
0.79
0.669 + 0.105
T.,8
0.23 + 0.029
0.625 + 0.193
0,786 + 0.012
0.704 + 0.118
S.
0.547 = 0.066
0.549 = 0.072
0.554 1 0.089
0.609 0.107
Te
0.534 = 0.066
0.534 + 0.072
0.577 + 0.054
0.55
S..B
0.351 = 0.032
0.394 + 0.070
0,844 + 0.017
+
T..B
0.370 + 0.047
0.514 + 0.158
0.758 + 0.029
0.872 0.216 0.216
S.
0.193 = 0.024
0,213 0.043
0.168 +
0.187 + 0.048
64
Ellipse
T
0.313 = 0.051
0.302 = 0.063
0.543 + 0.034
0.417 + 0.095
S.
0.356 = 0.043
0.498 0.125
0,894 + 0.011
0.157
T
0.351 = 0.054
0.548 0.174
0.702 + 0.026
0.280
S.
0.091 + 0.017
0.085 + 0.024
0.069 + 0.017
0.094 + 0.031
200
Te
0.092 = 0,018
0.084 + 0.024
0.369 0.042
0.239 + 0.091
S.
0,257 = 0,031
0.399 + 0.108
0.695
0.814 0.161
T,B
0.35 - 0.043
0.343 + 0.096
0.721 0.024
0,77 0.188
S.
01488 + 0.066
0.529 + 0.072
0,448 + 0.075
0.565
T
0.728 + 0.061
0.722 + 0.068
0.467 + 0.073
0.631 + 0.095
S.,
3.627 = 0.169
4.249 + 1.076
0.436 + 0.064
2.466 0.675
Gaussian
T,
3.601 + 0.171
4.290 + 1.114
0.410 + 0.052
3.043 0.677
S.
0.204 + 0.027
0.250 + 0.050
0.163 + 0.033
0.196 + 0.049
64
T
0.471 + 0.055
0.452 + 0.064
0.205 + 0.045
0.411 0.099
S.D
3.122 + 0.109
4.051 + 1.045
0,291 + 0.035
2.106 +
T.,
3.434 - 0.127
4.332 + 1.130
0.354 + 0.050
3,225
S.
0.095 = 0.017
0.116 + 0.038
0.065 + 0.019
0.102 + 0.032 0.032
200
T:
0.177 = 0.026
0.170 + 0.041
0.065 + 0.022
0.165 + 0.056
S.DB
3.46
4,421 + 1.108
0.352 + 0.048
2.069 0.718
T..B
3,297 0.112
4.206 + 1.096
0.333 + 0.044
3.018 0.59
S.
0.546
0.066
0.539 I 0.074
0.460 0,460 0.079
0.501
16
T,
0.622 0.060
0.571 0.071
0.51610.00
0.099
S..0
0.342 0.030
0.413 - 0.078
0.438 0.039
0.173
T..B
1.097 = 0.141
1.114 0.329
0.434 + 0.040
1.002 00220.40
S.
0.193 = 0.025
0.213 + 0.041
0.164 1 0.032
0.170 + 0.045
64
Gaussian Mixture
Te
0.197 = 0.025
0.205 + 0.039
0.182 1 0.036
0.174 1 0.046
S.
0.427 = 0.025
0.409 - 0.044
0.465 1 0.035
0.444 1 0.113
Te,
1.731 = 0.143
1.955 + 0.391
0.447 + 0.035
0.860 + 0.395
S.
0.093 = 0.017
0.103 + 0.030
0.073 0.019
0.084 + 0.028
200
T
0.097 = 0.018
0.093 + 0.025
0.084 0.025
0.091 1 0.032
S.
0.487 0.045
0.541 + 0.121 0.121
0.36610.000
0.717
T,
2.154 0.122
1.953 + 0.287
0.356 0.042
0.757 + 0.278
S:
0,562 + 0.065
0.544 0.073
0.485 + 0.085
0
16
T:
0.602 = 0.063
0.559 + 0.071
0.477 + 0.078
0.524 0.095
S.
0.349 0.031
0.412 0.097
0.360 + 0.037
+
T.B
1.883 = 0.188
2.458 0.684
0.391 + 0.049
1.525 + +.572
S.
0.194 = 0.026
0.220 + 0.045
0.162 + 0.032
0.177 + 0.047
64
Mixed
Te
0,202 = 0.025
0.228 + 0.046
0.168 + 0.034
0.188 + 0.051
S..B
0.265 = 0.032
0.351 + 0.087
0.285 + 0.04
0.592 + 0.224
T..8
0.977 = 0.102
1.622 + 0.448
0.336 + 0.042
1.276 + 0.455
S.
0.085 = 0.017
0.076 + 0.022
0.060 + 0.020
0.079 + 0.031
200
T
0.094 = 0.018
0.094 + 0.028
0.064 1 0.020
0.096 + 0.047
S..8
0.195 = 0.017
0.294 + 0.079
0.257 + 0.034
0.551 + 0.216
T:.6
3.092 = 0.164
2.999 + 0.699
0.314 + 0.041
1.575 + 0.424
29

---

Table 12: Results for minimum enclosing ball (2D). We report the relative error for the predicted radius (W.r.t to ground truth radius) (E,) and percentage of points excluded from the predicted enclosing ball (Ep). All processors are configured to output coarsened set of 16 points and frozen processors are trained on mixed synthetic data. Boldface indicates the best performing method while underlines denote best performing neural method.
Train Set
Architecture
&, 0.009 + 0.008
(%)
Sextent (Frozen)
1.9 1.3
Sextent (E2E)
0.023 + 0.019
2.3
Uniform
T Textent (Frozen)
0.099 + 0.050
0.100.
Disk
T extentt (E2E)
0.024 0.020
1.8
S Baseline (E2E)
0.048 + 0.028
0.5
Baseline (E2E)
0.030 = 0.024
0.0
Diieet
0.012 + 0.006
1.3
Direct
0.022 + 0.018
3.8
E-kernel Exact
0.000002 0.00009
0 0
Sextent (Frozen)
0.020 + 0.200
2.0
Sextent (E2E)
0.010 + 0.010
2.0
SQUID
eextent (Frozen)
0.068 + 0.045
1.6
T Textent (E2E)
0.190 0.090
4.0
Baseline (E2E)
0.027 0.025
2.8
T Baseline (E2E)
0.039 + 0.034
4.8
Direct
0.058 0.046
3.3
T Direct
0.685 + 0.065
83.3 - 10.7
e e-kernel Exact
0.00004 0.0006
Table 13: Results for minimum enclosing ball (3D). We report the relative error for the predicted
radius (E,) and the percentage of points which excluded from the estimated ball (%)). All frozen processors are trained on mixed synthetic data. Boldface indicates the best performing method while underlines denote best performing neural method.
Train Set
Architecture
E,
(%)
Sextent (Frozen)
0.030 + 0.020
0.7 + 1.0
Soxteut (E2E)
0.035 + 0.028
2.8 3.4
Textent (Frozen)
0.020
4.8
Uniform
Textent (E2E)
0.076
2.0
Ball
Baseline (E2E)
0.056
1.8 2.5
Baseline (E2E)
0.035 + 0.032
8.6 6.5
Spireet
0.014 + 0.011
1.6 + 1.5
Direet
0.028 + 0.017
+
e-errel Exact
0.001 + 0.003
0
Soxtent (Frozen)
0.100 + 0.070
0.2 + 0.7
Sextent (E2E)
0.060 + 0.050
0.2 0.9
Textent (Frozen)
0.077 0.072
1.3
Textent (E2E)
0.032
3.3 4.4
ModelNet
Basellne (E2E)
0.053 + 0.058
1.5
Baseline (E2E)
0.858 = 0.289
57.3 39.6
S Dtreet
0.214 0.179
8.1
Direet
0.033 + 0.02
3.6
8- -ernell + Exact
0.0005 + 0.0023
0.27 2.67
30

---

Table 14: Minimum enclosing ellipse error for point clouds in R on in-distribution test data, comparing frozen and end-to-end (E2E) training procedures. All frozen processors are trained on mixed synthetic data. We report the relative error in major (Er,maj) and minor radii (Er,min) and the percentage of points excluded (%)). Boldface indicates the best performing method while underlines denote best performing neural method.
Train Set
Architecture
Ex,min
Eaj
Ep (%)
Sextent (Frozen)
0.037 + 0.037
0.022 + 0.018
5.1 + 5.2
Sextent (E2E)
0.056 + 0.047
0.047 0.035
9.1 5.4
Synthetic
Textent (Frozen)
0.041 + 0.040
0.027
7.5
Ellipses
Textent (E2E)
0.038 + 0.033
0.022 = 0.019
6.3
Baselliee (E2R)
0.378 + 0.234
0.426 + 0.387
27.7 25.1
Bascline (F2E)
0.071 + 0.660
0.047 0.038
8.8
SDirect
0.033 + 0.025
0.039 0.022
9.8
Direct
0.035 = 0.03
0.025 = 0.019
6.6
e-kernel + Exact
0.0004 + 0.003
0.0001 = 0.0009
3.3
Sextent (Frozen)
0.056 + 0.047
0.047 = 0.035
6.6
Sextent (E2E)
0.078 + 0.065
0.050 - 0.038
1.2
Textent (Frozen)
0.058 0.051
0.032 0.026
6.6
SQUID
Textent (E2E)
0.093
0.045 0.034
7.7
Baseline (E2E)
0.322
0.250 0.262
32.0 16.6
Baseline (E2E)
0.049 0.041
16.8 18.4
D
0.684 + 0.729
0.049 0.039
0 0
Direct
1,483 + 1.287
0.128 = 0.064
1.8 0.7
e-kernel Exact
0.004 + 0.028
0.002 0.014
7.7 5.34
Table 15: Minimum enclosing annulus error on in-distribution test data, comparing frozen and end-to-end (E2B) training procedures. All frozen processors are trained on mixed synthetic data. We report the relative error in the width of the annuli and the proportion of points excluded
Train Set
Architecture
Ew
Ep (%)
Sextent (Frozen)
0.050 + 0.070
4.26
4.94
Sextent (E2E)
0.038 + 0.042
5.55
4.64
Synthetic
T Textent (Frozen)
0.077 0.104
11.39
+ 8.02
Annuli
Textent (E2E)
0.083 0.087
12.53 + 4.64
Spaseline
0.128 0.263
5.27 127
Baseline
0.417 = 0.574
1.39
Spirect
0.141 0.117
4.99 6.95
Direct
0.076 0.120
4.43 6.25
E-kernel + Exact
0.022 = 0.07
4.32
Sextent (Frozen)
0.073 = 0.110
6.31 4.15
Sextent (E2E)
0.087 + 0.103
8.42 + 4.64
Textent (Frozen)
0.064 + 0.084
9.60 4.75
SQUID
Textent (E2F)
+ 0.104+ 0.133
6.43 + 4.21
SBaseline (E2F)
0.191 + 0.219
7.23 5.04
Basellie (E2E)
0.118 0.120
11.9 6.86
Spirect
0.041 + 0.079
9.87 + 6.05
Tirrect
0.065 + 0.102
10.2 4.66
s-kemel + Exact
0.111 + 0.095
0.213 0.122
31

---

t-kemel size 16
e-kernel size 64
E-kennll size 200
04
03
04
4.5
030-
02-
332
055
01-
86
inputdimension
Impur dimendton
Ingut dimerdion
Figure 7: Directional width error (Ed vs. the input dimension of the point cloud. We train each model on 'Uniform Ball' datasets in IR? RR² and IR' and test on in-distribution dataset. We notice that all models, as well as the baseline algorithm have increasing directional width error as the input point cloud dimension increases.
R3
R3
36
10
10-4
4.0
4.5
5.5
3.5
4.5 4.5
5.0
3,5
3.5
4.5
5.8
B, 0.1
B,c. = 0.1 Sp
T,0
Figure 8: Directional width error (Edrr) a-fatness relaxed-e-kernel approximation task for R² and R We vary the a-fatness of the input data by varying the scale the minor axes of ellipsoids in 2 and R3 and then sampling point clouds from such ellipsoids. Each input point cloud has 100 points and the output e-kernels are fixed at 64.
g²
R²
0.20
0.30
0.2
0.30
313
0%
3.00
125
355
175
1.9
126
375
75
125
175
300
Output pkarrellsia
Output a-itrrma size
Output e-bernal size
Sco
TuB
B.R.E 0.1
Figure 9: Direction width error Edir vs output size of relaxed-e-kernel size across dimensions. All models are trained and evaluated point clouds sampled from uniform balls/disks with 500 points per set. Notice that, similar to the baseline algorithm, each model will have better results as we increase output point set size (with SumFormer implementation of Mg. still outperforming Transformer).
32

---

g²
0.2
0.20
9.3
0.59
1.40
0.00
4
0.4
640
3.08
088
2000
2000
2500
500
2009
Point
doud
9,00
7,,0
Figure 10: Directional width error &dir vs. input point cloud size. All models are trained on the uniform ball/disk dataset and evaluated uniform ellipses/ellipsoids of varying sizes.
30-1
70-1
(seconds)
(scconds)
Time (seconds)
00.2
390
2006
1.00
2000
2000
3000 3500
560
5000
1000
2009
1998
2000 3500
3000
2006
2000 2000
3500
3500
Point cloud size
Point cloud size
Point cloud size
Figure 11: Comparison of inference time for each model along with the runtime of the exact and approximate algorithms for coreset tasks.
Minimum Enclosing
Minimum Enclosing Fllisse
Minimum Enclesing Annulus
206
Pointt bloud 1k7m
Peint cloud wimw
Point clud size
Sueecc
Sootet
Tecter
T
Figure 12: Comparison of inference time for each model along with runtimes of the exact and approximate algorithms for extent measure tasks. Note that our model, Sextents is significantly faster than all classical algorithmic approaches.
Minimum Enclosing Ball
Minimum Enclosing Ellipse
Minimum Enclasing Annulus
4.00
Sucter (Frozent
Seaie (E2E)
Teaue E Frozent
Teowe (E2E)
Tasatine
Stwe
Toma
Figure 13: Size generalization across all extent measure tasks. We record the proportion of points missed by the predicted shapes produced by each model the extent-measure tasks as both the size and bounding box of the input point clouds increase.
33

---

Soces (Frozen]
Satee: (EZE)
Teve: (Frozen)
Festre (EZE)
Spwe
Firest
(a) Minimum enclosing ball.
(Frozen!
Duivel Salooaaaatremmmmm mousin
(b) Minimum enclosing ellipse.
Sucar (Frozen)
Seav:: (E2E)
Texure (E2E)
Sp mu
Tiwe
incheriouinn
Der-enhhit bunan
(c) Minimum enclosing annulus.
Figure 14: Visualizations for each extent measure problem. Notice that our frozen model performs much better ousttf-distribution than other comparable neural models.
34

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providded a proper justification is given (e.g., "error bars expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer often more nuanced, so please just use your best, judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In sections 3 and 4, we introduce our neural frameworks approximating solutions for extent measures of point clouds. We also introduce our relaxed-s-kema theory in sections and Finally, we show that our neural networks can produce e-kennel approximations in the section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
35

---

Answer: [Yes]
Justification: we discuss limitations of the work in the conclusion. In each theorem, we point out the assumptions made the point clouds (e.g. a-fatness).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell--pecfiicaion. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-texl system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
All proofs are given in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The entire experimental set-up is given the appendix and we provide the code well.
36

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: As stated previously, we provide the code as well as all the synthetic benchmark datasets. The real datasets are freely available online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
public/ /twpg///iddddeiiieeeeeee
Sewuuiissionsi sww.niisssiniiiiyyccccomm.mmmmcc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NewrIPS code and data submission guidelines (https
cirips.cc/publiee http://uwwcccgiidee////ees SoodeSuuuaaa as i oonooooiiiooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
37

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The train and test details are given in the beginning of Appendix A.4
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We report error bars in all tables.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We specify the type/number of GPUs needed in Appendix A.4
Guidelines:
The answer NA means that the paper does not include experiments.
38

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https::/ http://sssppccbbccccccccccccaaaa
Answer: [Yes]
Justification: Yes, we believe we have conformed with the NeurlPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work concerns mainly approximation theory and neural network archi- tectures for computational geometric primitives. We see mechanism by which neural e-kernels could cause negative impacts. Our paper is not tied to any applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
39

---

Answer: [NA]
Justification: All of our real world data is already publicly available. The SQUID and ModelNet do not have high risk for misuse as they have already been highly curated and have no unsafe point clouds/images.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We properly cite ModelNet and SQUID.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, ppapersw thoode com / datt asets has curated licenses for some datasets. Their licensing guide help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do release any new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
40

---

14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our research does involve any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMss if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
This paper does not describe the usage of LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
//te:///nrrriiee httperrrppps.cccccaaaeeeeeeee//e 2005/ L.L.) for what should should not be described.
Please refer to our LLM
41


Reviews:
[{"review_id": "21BNfbaL17", "reviewer": "Reviewer_WDZw", "summary": "This paper defines the relaxed-$\\varepsilon$-kernel as a kind of universal coreset for approximating faithful extent measures. The paper then generalizes this approach to unfaithful extent measures via a polynomial lifting/linearization trick. It is shown that a sumformer can approximate an algorithm to compute a relaxed kernel. This motivates the design of an architecture to approximate kernels, which, when composed with a learned encoder and decoder, can be used to approximate extent measrues. The experimental results compare a few architectures and training protocols on the tasks of learning to approximate kernels and extent measures.", "questions": "- If I understand correctly, the complexity of Algorithm 1 is bounded in the number of input points, but scales exponentially with the dimension $d$. Isn't this the more pernicious scaling? Standard algorithms for convex hull etc. work just fine on a large number of points in low dimension (2 or 3). In what context do you envision your method or model being used. In other words, in what range of dimensions, approximation quality $\\varepsilon$, etc. is the approximation/time tradeoff reasonable?\n- The fatness of the point set is also an important scaling parameter. Does the fatness not scale with the number of points in the worst case?\n- What exactly do you mean by the \"alignment\" or \"resemblance\" of a model with an algorithm? I can see how you can design very specific model weights to enact the algorithm, as you do to prove Theorem 3.4. But this is just rewriting the algorithm in a different language. Does the fact that you can do this by hand somehow imply that the model class should generically learn to enact the approximation algorithm you want? Or at least that it will learn to approximate the algorithmic result better than any other model architecture would?\n- Does the alignment happen in practice? I.e., can you see if the learned weights agree with the ones you would impose by hand to encode the approximation algorithm?\n- In Algorithm 1, the required $\\delta$-net size still scales exponentially with $d$. Doesn't this pose a problem for the bounded model complexity?\n- Did you try any experiments in dimension higher than 5? In high dimension is presumably where the scaling performance would really start to matter.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "It seems the paper's most important contribution is in defining and proving results about relaxed $\\varepsilon$-kernels. However, this is outside my usual domain of expertise, and I am not sure how much of a contribution this is relative to previous work in computational geometry. This paper might receive more careful and incisive peer review at a computational geometry conference rather than NeurIPS.\n\nI am skeptical of the learning aspect of this work, and in particular of the whole \"algorithmic alignment\" idea. It seems the argument is that because a particular architecture X (in this case based on the sumformer) is capable of enacting a particular algorithm Y, that therefore X will learn to approximate Y during training. I don't see why this follows. Since no theoretical justification for this claim is provided (nor would I expect it would be possible to prove something like this), it seems like more rigorous empirical evaluation of the learning claim is merited.\n\nIf it were the case that the kernel approximation network were really learning to approximate Algorithm 1 to compute relaxed-$\\varepsilon$-kernels, I'd expect it to have nearly perfect generalization to arbitrary input point clouds. However, in Figures 9 and 10 in the appendix, test error appears to get worse during training for the two OOD datasets. This suggests that the model is not actually learning a universal algorithm for computing relaxed $\\varepsilon$-kernels, but rather is learning some heuristics that work on a particular dataset.\n\nOn a more philosophical note, given that Algorithm 1 is simple and efficient and that it comes with hard theoretical guarantees, what is the advantage of learning to approximate Algorithm 1? Even if it were guaranteed that the kernel approximation network would learn to approximately enact Algorithm 1, it would still be more efficient and reliable just to use Algorithm 1 directly.", "was_revised": true, "final_justification": "I appreciate the authors' responses and new experiments. I understand better the value of the learned model over the classical approximation algorithm.", "rebuttal": "Thank you for your time and careful review! We are glad the reviewer appreciates our introduction of the relaxed-$\\varepsilon$-kernel.  \n\n**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.  \n\nIn 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.  \n\nSimilar 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.  \n| **Method**           | **200**        |               | **400**        |               | **800**        |               |\n|----------------------|----------------|---------------|----------------|---------------|----------------|---------------|\n|                      | Runtime        | Error         | Runtime        | Error         | Runtime        | Error         |\n| $\\mathcal{S}\\_\\varepsilon$ (ours) | **0.0002**     | **0.081**     | **0.0005**     | **0.088**     | **0.0003**     | **0.105**     |\n| Relaxed ε-kernel     | 0.0007         | 0.145         | 0.0007         | 0.148         | 0.0013         | 0.162         |\n| ε-kernel             | 0.0009         | 0.085         | 0.0010         | 0.099         | 0.0013         | 0.111         |\n\nAdditionally, 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.  \n\nFinally, 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.  \n\n[1] *The CLRS Algorithmic Reasoning Benchmark* (Veličković et al., ICML 2022).  \n[2] *Neural Execution of Graph Algorithms* (Veličković et al. ICLR 2020).  \n[3] *Learning Graph Algorithms with Recurrent Graph Neural Networks* (Grötschla et al. GCLR Workshop @ AAAI 2023).  \n\n**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*.  \nScaling 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.  \n\n**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).  \n\n**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.  \n\n**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."}, {"review_id": "PmBuDKziAV", "reviewer": "Reviewer_QaAt", "summary": "This manuscript proposes a way of approximating certain quantities about point clouds with bounded model complexity (and linear runtime complexity). It does so by introducing the concept of “relaxed epsilon-kernel”, which unlike the traditional epsilon-kernel can be built out of points in the entire convex hull, not a subset of the point cloud. This approach is evaluated in a thorough way theoretically and in practical examples.", "questions": "What theoretical effects does changing the L1 normalization for a softmax have? Which results remain valid, and which are not? As a reader, I was a bit perplexed by this choice, and while I am convinced by the results that it is in practice better, I was left wondering how much of the prior 3 sections are actually theoretically justified when one performs this change.\n\nWhat are some examples of unfaithful extent measures that one can keep in mind when reading the text? What are some examples of linearizable and non-linearizable ones? Adding such examples in the text will make Sec. 4 feel much more grounded.\n\nTo clarify: once trained, the same trained network can be used to process point clouds of different sizes, correct?\n\nWhat does the “hyperparameter search” entail?\n\nWhat is the (input) noise sensitivity of this entire pipeline?", "limitations": "In my opinion, the main limitation of the work is its applicability: it is relevant only for a small number of “simple” point cloud operations (as opposed to, e.g., reconstruction or triangulation), and likely has diminishing returns as the dimension of the data approaches the number of data points. That being said, these limitations are discussed accurately and openly, and I do not penalize this work for it.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The main strength of the work is the theoretical contribution of introducing relaxed epsilon kernels and their relationship to commonly-used neural architectures. These seem like important contributions to the study of point clouds from the computational geometric perspective, and I can imagine they will inspire future work in this direction. Another major strength is the evaluation: all theoretical results are conclusively proven, including careful tracking of bounds and infinitesimal constants. The practical evaluation of the method in the supplemental also goes well beyond what is expected of such a theoretically heavy manuscript.\n\nI will preface this by saying that I am not an expert on computational geometric problems like this one, so there is definitely a chance I missed a mistake in a proof or some other major limitation. I will carefully read other reviewers’ comments as well as the authors’ response.\n\nNonetheless, I could not find any major issue in this work. If anything, the sole reason I would not rank this manuscript higher is the didactic exposition of the method. For something as visual as point cloud processing, there is a single didactic figure (Fig. 3), and I cannot understand exactly what it is showing. What is u? Where is the origin, so I can understand p as a vector? Also, the font is way too small. I would really much prefer if all of sections 2 and 3 were followed by a study of the same didactic 2D point cloud: it would make an intuitive understanding of the concepts significantly easier.\n\nI would also encourage the work to be double-checked for typos (e.g., “computatoin”) and missing articles.", "was_revised": true, "final_justification": "The authors have resolved all my concerns, and I remain generally positive about this work. At the same time, other reviewers (with potentially more expertise in this topic than me) have raised what sound like reasonable concerns, so I look forward to hearing their opinion on the rebuttal conversation", "rebuttal": "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. \n\n**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. \n\n**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. \n\n**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.\n\n**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\\}$. \n\n**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). \nAdditionally, 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."}, {"review_id": "XUaqeQZOym", "reviewer": "Reviewer_VDgZ", "summary": "This paper proposes a neural approach to address geometric \"extent measure\" problems. A key contribution is the introduction of the relaxed-ϵ-kernel, with a neural network employed as the fitting function. The effectiveness of the approach is demonstrated through experiments conducted on both synthetic and real datasets.", "questions": "* Could the author provide a more detailed discussion of the motivation?\n* The related work section is essential, but it is currently missing.\n* It is necessary to include comparisons with neural baselines and extensive classic baselines.\n* Adding more visual comparisons would be helpful to verify that the proposed method achieves reasonable performance.", "limitations": "Yes.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n* This work presents a neural solution for addressing geometric \"extent measure\" problems, which is an interesting attempt.\n* The paper includes some theoretical analysis.\n\nWeaknesses:\n\n* The motivation behind this work is unclear. The geometric \"extent measure\" problem is a well-studied area. It is not evident what specific advantages a neural solver brings to this problem. Furthermore, there is no discussion about the potential benefits of the proposed approach.\n* The lack of a related works section makes it difficult for readers to evaluate the distinct innovations of the proposed method compared to existing approaches.\n* There is a lack of comprehensive comparisons. The experimental section only includes results from some proposed neural variants, which does not sufficiently verify the effectiveness of the proposed method over existing works.\n* Important experimental results are missing. Specifically, there is no time analysis or visual results, which limits the readers’ ability to fully understand the effectiveness and utility of the proposed method.", "was_revised": true, "final_justification": "I appreciate the effort made by the authors to provide additional results. However, I would like to emphasize that my major concern remains unresolved:\n\n- Very Limited \"Related Work\" in Paper: Although the authors included a \"related work\" paragraph focusing on the neural methods, they did not provide a discussion about the differences between the proposed algorithm and traditional algorithms. \n\n- 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.\n\n- 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.\n\n\nAs a result, I believe the current draft is not yet ready. The motivation and contribution remain unclear, and the effectiveness is inadequately demonstrated.", "rebuttal": "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. \n\n**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. \nIn 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. \n\nFirst, 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. \nOur 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 \\textit{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]). \n\nImportantly, 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). \n\nIn 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. \nWe will be happy to revise our Introduction to make these points more clear.\n\n[1] \"Computing Instance-Optimal Kernels in Two Dimensions\" (Agarwal and Har Peled, Discrete and Computational Geometry 2024)\n\n**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. \nFirst, 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 \\textit{independent} of the input point set size using our specific sumformer architecture. \n\n[1]\"Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem\" (Amir, et al. NeurIPS 2023)\n\n**Regarding Q3, baselines:** Thank you for your suggestion regarding comparing to more neural and algorithmic baselines. \nTo 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.\nThe 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. \n\nTo 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. \nTo 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). \n| **Model** | $\\mathcal{E}\\_{r}$ | $\\mathcal{E}\\_\\mathrm{p}$ |\n|-|-|-|\n| $\\mathcal{S}\\_\\mathrm{Direct}$ | 0.986 ± 0.004  | 1.000 ± 0.000  |\n| $\\mathcal{S}\\_\\mathrm{extent}$ (frozen) | **0.065 ± 0.055** | **0.052 ± 0.056**  |\n|$\\mathcal{S}\\_\\mathrm{extent}$ (E2E) | 0.428 ± 0.057 | 0.596 ± 0.106 |\n| $\\mathcal{S}\\_\\mathrm{Baseline}$  | 0.687 ± 0.080| 0.881 ± 0.089|\n\nAdditionally, 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. \n\n**Table B**. Comparison of extent measure model against algorithmic baselines\n| **Method** | **200**| | **600**| |\n|-|-|-|-|-|\n|   | Runtime | Error| Runtime| Error|\n| $\\mathcal{S}\\_\\mathrm{extent}$ (frozen) | **0.0004** | 0.020    | **0.0007**     | 0.028       |\n| Welzl's  algorithm | 0.0203 | **0** | 0.0607  | **0** |\n| ε-kernel + Welzl's algorithm   | 0.0022  | 0.0002 | 0.0031| 0.0002 |\n| $\\mathcal{S}\\_\\mathrm{Baseline}$| 0.0011| 0.020| 0.0100| 1.900 |\n\nAdditionally, 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).\n\n**Table C**. Comparison of $\\mathcal{S}\\_\\varepsilon$ against baselines\n|Method|200| |400| |800| |\n|--|--|--|--|--|--|--|\n| |Runtime|Error|Runtime|Error|Runtime|Error|\n|$\\mathcal{S}\\_\\varepsilon$|**0.0002**|**0.081**|**0.0005**|**0.088**|**0.0003**|**0.105**|\n|Relaxed ε-kernel|0.0007|0.145|0.0007|0.148|0.0013|0.162|\n|ε-kernel|0.0009|0.085|0.0010|0.099|0.0013|0.111|\n|$\\mathcal{S}\\_\\mathrm{Direct}$|0.0016|0.509|0.0007|0.451|0.0006|0.373|\n\nWe will include more comparisons with both classical algorithmic and neural baselines for extent measure problems in our final manuscript.\n\n[1] \"Relational Inductive Biases, Deep Learning, and Graph Networks\" (Battaglia, et al. 2018)\n\n**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."}, {"review_id": "yS0SV5jYhd", "reviewer": "Reviewer_r5xy", "summary": "This paper introduces a novel approach for approximating \"extent measures\" in computational geometry with neural networks. It develops a \"relaxed $\\epsilon$ theory\" which can be implemented using a neural network (SumFormer) with a bound on the number of parameters. The framework encodes input points into a latent space where they are processed using a SumFormer-based model. The model size is only dependent on the input point dimension, not on the number of points in the set, and a bound on the model parameters, depending on a user-specified approximation error, is derived.\n\nThis latent space model is then tested on both synthetic data for validation and real datasets (SQUID [a fish boundary contour dataset] and ModelNet). The experiments test multiple latent processing models and training schemes (transformer, sumformer, end-to-end, frozen processing model) with mixed results and performance on both in and out of distribution points. The appendix provides further results on varying sampling schemas and set sizes.", "questions": "I'm not an expert on point cloud geometry. Reading your paper, I have the following questions:\n\n- How strong is the assumption of \"fat\" point clouds in practice? Are there important cases where this assumption doesn't hold?\n\n- Can you provide a comparison to a classical baseline (algorithms using $\\epsilon$-kernels$?), both in terms of performance and compute requirements/scaling?\n\n- Are there any deep learning baselines to compare to?\n\n- The SQUID dataset seems a bit odd (fish boundary contours?). Can this method also be applied to noisy real-world data, such as lidar scans?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- Good structure\n\n- Clear theory development and implementation thereof. Theory from the initial definition to theorems can be followed by someone not familiar with the topic.\n\n- Robost framework, which can handle point clouds of varying sizes\n\n- The latent space processing model can be retrained on new data/task by simply retraining the encoder/decoder.\n\n## Weaknesses\n\n- Derivations require \"fatness\" of the point cloud, not clear how much of a restriction this is in practice.\n\n- Missing Baselines: No deep-learning baselines and \"none-neural\" baselines.", "was_revised": true, "final_justification": "I think a novel application with strong theoretical contributions should be included at NeurIPS. Yeah they have high errors, but e.g. PDE-surrogates also were not competitve with traditional PDE solvers in the first paper. Geometry processing is always in need of more speed, so for me the motivation is clear (I disagree with reviewer VDgZ here). \n\nMain problem with the initial submission was insufficient comparison to classical baselines, but this was provided in the rebuttal.", "rebuttal": "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.\n\n**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.\nOur 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). \n\n\n**Regarding Q2, baselines:** Thank you for your suggestion regarding comparing to more neural and algorithmic baselines. We will reiterate our response to Reviewer VDgZ. \nTo 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.\nThe 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. \n\nTo 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. \nTo 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). \n| **Model** | $\\mathcal{E}\\_{r}$ | $\\mathcal{E}\\_\\mathrm{p}$ |\n|-|-|-|\n| $\\mathcal{S}\\_\\mathrm{Direct}$ | 0.986 ± 0.004  | 1.000 ± 0.000  |\n| $\\mathcal{S}\\_\\mathrm{extent}$ (frozen) | **0.065 ± 0.055** | **0.052 ± 0.056**  |\n|$\\mathcal{S}\\_\\mathrm{extent}$ (E2E) | 0.428 ± 0.057 | 0.596 ± 0.106 |\n| $\\mathcal{S}\\_\\mathrm{Baseline}$  | 0.687 ± 0.080| 0.881 ± 0.089|\n\nAdditionally, 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. \n\n**Table B**. Comparison of extent measure model against algorithmic baselines\n| **Method** | **200**| | **600**| |\n|-|-|-|-|-|\n|   | Runtime | Error| Runtime| Error|\n| $\\mathcal{S}\\_\\mathrm{extent}$ (frozen) | **0.0004** | 0.020    | **0.0007**     | 0.028       |\n| Welzl's  algorithm | 0.0203 | **0** | 0.0607  | **0** |\n| ε-kernel + Welzl's algorithm   | 0.0022  | 0.0002 | 0.0031| 0.0002 |\n| $\\mathcal{S}\\_\\mathrm{Baseline}$| 0.0011| 0.020| 0.0100| 1.900 |\n\nAdditionally, 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).\n\n**Table C**. Comparison of $\\mathcal{S}\\_\\varepsilon$ against baselines\n|Method|200| |400| |800| |\n|--|--|--|--|--|--|--|\n| |Runtime|Error|Runtime|Error|Runtime|Error|\n|$\\mathcal{S}\\_\\varepsilon$|**0.0002**|**0.081**|**0.0005**|**0.088**|**0.0003**|**0.105**|\n|Relaxed ε-kernel|0.0007|0.145|0.0007|0.148|0.0013|0.162|\n|ε-kernel|0.0009|0.085|0.0010|0.099|0.0013|0.111|\n|$\\mathcal{S}\\_\\mathrm{Direct}$|0.0016|0.509|0.0007|0.451|0.0006|0.373|\n\nWe will include more comparisons with both classical algorithmic and neural baselines for extent measure problems in our final manuscript.\n\n[1] \"Relational Inductive Biases, Deep Learning, and Graph Networks\" (Battaglia, et al. 2018)\n\n**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.\nAdditionally, 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."}]

Author rebuttal:

Meta-review: This paper proposes an approach for approximating "extent measures" in computational geometry using neural networks. Initially, the paper received one Reject and three Borderline Accept ratings. The reviewers appreciated the theoretical contribution coupled with the implementation, but raised concerns about the relatively limited quantitative evaluation and the limited discussion of related work. The rebuttal initiated further discussion, and in general the reviewers responded positively, with the paper eventually receiving one Reject, one Borderline Accept, and two Accept ratings. The reviewer advocating for rejection felt that the paper is not yet ready for publication and requires more careful evaluation. However, the other three reviewers valued the theoretical contribution, the practical demonstration, and the well-motivated approach. Based on this balance of opinions, the AC sides with the majority and recommends acceptance. Authors should still consider any additional comments or feedback from the reviewers while preparing their final version and of course update the manuscript to include any additional promised changes, analysis, results and/or discussion they provided in their rebuttal, particularly the extended quantitative evaluation results.
Decision: Accept (poster)