ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS
Authors: Sujoy Bhore
Devdan Dey
Satyam Singh
Venue: ICLR 2025 Poster (2025)
Keywords: Theoretical machine learning
VC-dimension
Geometric sampling
Primary area: learning theory

Abstract: VC-dimension (Vapnik & Chervonenkis (1971)) and $\varepsilon$-nets  (Haussler & Welzl (1987)) are key concepts in Statistical Learning Theory. Intuitively, VC-dimension is a measure of the size of a class of sets. The famous $\varepsilon$-net theorem, a fundamental result in Discrete Geometry, asserts that if the VC-dimension of a set system is bounded, then a small sample exists that intersects all sufficiently large sets.
    
    In online learning scenarios where data arrives sequentially, the VC-dimension helps to bound the complexity of the set system, and $\varepsilon$-nets ensure the selection of a small representative set. This sampling framework is crucial in various domains, including spatial data analysis, motion planning in dynamic environments, optimization of sensor networks, and feature extraction in computer vision, among others. Motivated by these applications, we study the online $\varepsilon$-net problem for geometric concepts with bounded VC-dimension. While the offline version of this problem has been extensively studied, surprisingly, there are no known theoretical results for the online version to date. We present the first deterministic online algorithm with an optimal competitive ratio for intervals in $\mathbb{R}$. Next, we give a randomized online algorithm with a near-optimal competitive ratio for axis-aligned boxes in $\mathbb{R}^d$, for $d\le 3$. Furthermore, we introduce a novel technique to analyze similar-sized objects of constant description complexity in $\mathbb{R}^d$, which may be of independent interest. 
    
    Next, we focus on the continuous version of this problem (called online piercing set), where ranges of the set system are geometric concepts in $\mathbb{R}^d$ arriving in an online manner, but the universe is the entire ambient space, and the objective is to choose a small sample that intersects all the ranges. Although online piercing set is a very well-studied problem in the literature, to our surprise, very few works have addressed generic geometric concepts without any assumption about the sizes. We advance this field by proposing asymptotically optimal competitive deterministic algorithms for boxes and ellipsoids in $\mathbb{R}^d$, for any $d\in\mathbb{N}$.

Published as a conference paper at ICLR 2025
ONLINE EPSILON NET & PIERCING SET FOR GEOMETRIC CONCEPTS*
Sujoy Bhore'
Devdan Dey!
Satyam Singh
ABSTRACT
VC-dimension (Vapnik & Chervonenkis (1971)) and e-nets (Haussler & Welzl (1987)) are key concepts in Statistical Learning Theory. Intuitively, VC-dimension is measure of the size of a class of sets. The famous E-ner theorem, fundamental result in Discrete Geometry, asserts that if the VC-dimension of set system is bounded, then a small sample exists that intersects all sufficiently large sets.
In online learning scenarios where data arrives sequentially. the VC-dimension helps to bound the complexity of the system, and e-nets ensure the selection of a small representative set. This sampling framework is crucial in various domains, including spatial data analysis, motion planning in dynamic environments, opti- mization of sensor networks, and feature extraction in computer vision, among others. Motivated by these applications, we study the online e-ner problem for ge- ometric concepts with bounded VC-dimension. While the offline version of this problem has been extensively studied, surprisingly, there are no known theoreti- cal results for the online version to date. We present the first deterministic online algorithm with an optimal competitive ratio for intervals in IR. Next, we give a ran- domized online algorithm with near-optimal competitive ratio for axis aaisnel boxes in Rd, for d < 3. Furthermore, we introduce a novel technique to analyze similar-sized objects of constant description complexity in Rd which may be of independent interest.
Next, we focus on the continuous version of this problem (called online piercing sef), where ranges of the set system are geometric concepts in Rd arriving an online manner, but the universe is the entire ambient space, and the objective is to choose a small sample that intersects all the ranges. Although online piercing set is very well-studie problem in the literature, to our surprise, very few works have addressed generic geometric concepts without any assumption about the sizes. We advance this field by proposing asymptotically optimal competitive deterministic algorithms for boxes and ellipsoids in Rd, for any d E N.
INTRODUCTION
The concepts of Vapnik- Chenk--Cherronnnis dimension (VC-dimension) and E-net theory are fundamen- tal components in Statistical Learning Theory. VC-dimension, introduced by Vapnik & Chervo- nenkis in their seminal work Vapnik & Chervonenkis (1971), is tighter measure of the com- plexity of concept classes. We need some key definitions to discuss the notion of VC-dimension formally. A set system (also known range space) (X, R) is defined by a set X and class R. (known as ranges) of subsets of X. For instance, consider a set system: X' = {1, 2,3, 3,44 4] and R = ( 2). {2, 3), {2, 3, 4), {1, 4] (see also Figure for a geometric example). In learning theory, the set X' is the instance space, and R is the class of potential hypotheses, where a hypothesis r is a subset of X. set system R) shatters set A each subset of A can be expressed as A for some in R. The VC-dimension of R is the size of the largest set shattered by R. Due to Vapnik & Chervonenkis (1971), it known that for any range space (X, R) with VC-dimension bounded by constant d, for any > 0. randomly chosen small subset of X' will hit every range containing at least e|.X'| points from X, with high probability. Haussler Welzl (1987) showed that the size of the small subset. called e-ner (for formal definition, Definition I in Section 2), is bounded by O ( log ) where is the VC-dimension of the range space. This result is famously
'll authors contributed equally. 1 Department of Computer Science and C-MInDS, Indian Institute of Technology Bombay, Mumbai, India Email: sujer sujoy. bhorre i 1 com.
I Department of Computer Seience & Engineering, Indian Institute of Technology Bombay, Mumhai, India
Email: mnz, devdann d 1
com.
$ Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumhai, India.
Email: satyari t:d1 98gma com.

---

Published as a conference paper at ICLR 2025
known as the E-net theorem, and is a celebrated result in Discrete Geometry. One of the central open questions in the theory of E-nets is whether the logarithmic factor log 1 in the upper bound on their size is truly necessary. Pach & Woeginger (1990) showed for d 2 2. logarithmic factor is necessary, but d = the net size can be bounded by max (2, L 1). In the last three decades, remarkable progress has been made on the size of e-net for geometric set families by exploiting various intrinsic geometric properties (we briefly discuss these results in Section 1.1).
In this work, we focus on the s-net problem in the online setup. In the online s-net problem, the set X' is known in advance, but the objects of R. arrive one at a time, without advance knowledge, and we need maintain valid net N C X for the input objects. The performance of an online E-ner algorithm is measured by the competitive ratio, which is (informally) defined as the maximum ratio between the performance of the algorithm and the offline optimal net (see Section for a formal definition).
Besides its underlying deep theoretical nature, online E-nets have found many applications in mod- machine learning, particularly in areas like active learning, adversarial robustness, efficient sam- pling, etc. In active learning, E-nets help to select representative samples from large datasets. This process allows the models to be trained with minimal labelled data while maintaining accuracy (see, e.g., Hanneke & Yang (2015); Balcan et al. (2010)). Morcover, online E-nets play an important role in adversaria robustness by covering potential adversarial regions of the input space, ensuring that models are less susceptible to attacks (see, e.g., Madry et al. (2017); Cullina et al. (2018); Montasser al. (2019)). In this work, we primarily foeus the theoretical aspects of online e-nets, which form a crucial component of Statistical Learning Theory, contributing to our understanding of gen- eralization, sample complexity, and robustness in machine learning models (Vapnik (2013); Laan et al. (2006)).
Figure 1: An example of geometric range space (X, R). Here, the set X' is the collection of points,
while R is the collection of rectangles.
Continuous Setup: Towards Piercing Set. Given a set R of n geometric objects in Rd, a subset
P C Rd is a piereing set of R if every object of R contains least one point of P. The minimum piercing set (MPS) problem asks for a piereing set P of the smallest size. The problem has numerous applications in facility location, wireless sensor networks, learning theory, etc. See Sharir & Welzl (1996); Huang et al. (2004); Ben-Moshe et al. (2000); Katz et al. (2003); Mustafa (2022). The problem can be viewed as a "continuous" version of --net problem, also known as the geometric hitting set problem. The geometric hitting set, in turn, corresponds to geometric set cover in the dual range space'. Hence, by the standard greedy algorithm for set cover, one can compute an Olog r) -aprroximationn to the minimum piercing set in polynomial time for any family of piercing set with constant description complexity (since suffices to work with a discrete set of (nn) candidate points). For geometric set families, range of sophisticated approximation schemes have been proposed over the years (see Section 1.1 for a brief discussion).
In online piercing set, the point set Rd is known beforehand, but the set R of geometric objects is not known in advance. Here, the geometric objects arrive one by one. An online algorithm must maintain a valid piercing o, the algorithm must maintain a valid piercing set. Note that an online algorithm may add points to the piercing set but cannot remove points from it, i.e., all the decisions taken by the algorithm are irrevocable. The problem aims to minimize the cardinality of the piereing set. In the online hitting set, X' C Rdd such that | n. Charikar et al. (2004) initiated the study of the online piercing set problem for unit balls in Rdd They proposed an online algorithm having a competitive ratio (d log d). Moreover, they proved that (log d/ log log log df) is the (deterministic) lower bound of the competitive ratio for this problem. Later, Dumitrescu et al. (2020) improved both the
for all objects arrived so far. Upon the arrival of new object
"Given a finite family R of ranges in Rd, the dual range space induced by them is defined as set system on the underlying set R. consisting of the sets R₂ == [R] x E R. E R.), for all Rd.
2

---

Published as a conference paper at ICLR 2025
upper and lower bounds of the competitive ratio to (1.3211 and 2id + 1), respectively. For unit hypercube in R", Dumitrescu& & Tóth (2022) proved that the competitive ratio of any deterministic online algorithm for the unit covering problem is at least 2". Then, for integer hypercubes in R', they proposed a randomized online algorithm with a competitive ratio of (dd) and a deterministic lower bound of d + 1. For similar size o-fat objects in RR, De et al. (2024a) gave a deterministic algorithm with competitive ratio O( + 2)d log M), and a lower bound of S2(d log M + 22).. Note that a set S is said to be similarly sized a-fat objects when the ratio of the largest width of an a-fat object (for the definition of a-fat object, see Section 2) in S to the smallest width of an a-fat object in S is bounded by fixed constant M > See Section 1.1 for further discussion on this.
An online E-ner can be viewed as specific type of online piercing set where the focus is on main- taining coverage with respect to the measure of the sets rather than merely ensuring intersection. Consequently, both structures aim to address the complexities of dynamic data scenarios by provid- ing robust sampling and representation mechanisms.
1.1 RELATED WORK
The s-net theory has seen remarkable growth in the last few decades. Here, we provide a very concise summary of this. Matoušek (1992) demonstrated that for range spaces (X, R) where X' is a finite set of points in R2 (or R3) and R consists of half-spaces, the size of the E-net can be reduced to (((2) eliminating the logarithmic factor. Aronov et al. (2009) showed the exis- tence of e-nets of size O (2 log log 2) for planar point sets and axis-aligned rectangles. Clarkson & Varadarajan (2005) made an important breakthrough by establishing connection between the size of g-nets for dual range space (X', R) associated with geometric objects and their union complexity". In particular, they showed if the union complexity is o(n n.) then dual set systems admit e-net of size o(1/e (oT//log(1//)) log(1/e)). On the lower bound side, one can typically find approximately 1/e pairwise disjoint, s-heavy ranges in R. For these cases, the size of any s-net must be at least Q (2). For many years, it has been widely conjectured that for geometric set families, this bound is tight (see Matoušek et al. (1990)). Alon (2012) proved the conjecture false by giving examples of geometric range spaces of small VC-dimension, e.g., straight lines, rectangles, or infinite strips in the plane, that do not have e-net of size (1)s). Later, Pach & Tardos (2011) showed that range spaces with VC-dimension 2 have a smallest E-net of size (11 log L/E). They also proved lower bound on size of E-net for axis parallel rectangle in R² is 211/= log log 1/E).
E-net:
Piercing Set. In the offline setting, the piercing set problem is a well-studied problem in Com- putational Geometry. The problem is NP-complete even for a set of unit squares Garey & Johnson (1979). For geometric set families, e.g., unit squares/hypercuhes, unit disks/balls, or more generally, near-equal-sized fat objects in IR4, various approximation schemes have been developed; see Chan (2003); Efrat et al. (2000); Katz et al. (2003)). For arbitrary boxes in Rd, the current best approxi- mation scheme is via E-ner (see Agarwal et al. (2024)). Recently, Bhore & Chan (2025) obtained dramatic improvement over the running time.
Online Piercing & Hitting. Alon al. (2009) in their seminal work initiated the study of the hitting set problem in the online setting. They proposed an online algorithm having a competitive ratio of Olog n log m), where | and [R] = m. Moreover, they establish nearly matching Ω log m log log log m++log logn lower bound for the problem. In the geometric setting, Even & Smorodinsky
(2014) proposed online algorithms having an optimal competitive ratio of (loog n). where X is finite subset of points and R consists of half-planes in R.2, and also when consists of unit disks. Khan et al. (2023) obtained an optimal O(log N)-competitive algorithm when X' is a finite set of points from 2² and R consists of integer squares (whose vertices have integral coordinates) S C [0, 22 in R² Recently, De et al. (2024b) also obtained an optimal competitive ratio of Ollgg n) when X is a finite set of points from IR' and R consists of translates of either a disk or regular& k-gon. For a special case, when the point set is entire Zz, De & Singh (2024) studied the problem for unit balls and hypercubes in IR Alefkhani et al. (2023) considered this variant for f-fat objects in N),, and proposed a deterministic online algorithm with competitive ratio of ( + 1)2d log N. Recently, De et al. (2024b) obtained improved upper and lower bounds.
Thhe complexity of the boundary of the union of set of objects (sce Clarkson & Varadarajan (2007)).
3

---

Online piercing set. Starting from the work of Charikar et al. (2004), online piercing set has been studied extensively over the years (see Dumitrescu et al. (2020); Dumitrescu & Tóth (2022)). However, it is impossible to obtain sublinear competitive ratios for any geometric families due to a hopeless lower bound of (2()). which even holds for arbitrary intervals. where n. is the length of the imput sequence. Several works addressed this issue by making assumptions on the object types (famess) or aspect ratio of the input objects (see De et al. (2024a); Khan et al. (2023)). Surprisingly, very little is known when these constraints do not hold. We present the first deterministic online al- gorithm for axis-aligned boxes and ellipsoids in IR with an optimal competitive ratio of Ollog M). These results are asymptotically tight due to the existing lower bound of 22 M) for hypercubes and balls in IRd (De al. (2024b)). Additionally, we introduce a novel technique to analyze similar- sized fat objects of constant description complexity in Rd Although the result slightly improves the existing upper bound of De et al. (2024a), we believe the technique may be useful other on- Published as a conference paper at ICLR 2025
1.2 OUR CONTRIBUTIONS.
We study the online E-ner and online piercing set for a wide range of geometric objects. For some of the objects, we designed online algorithms which achieve asymptotically tight competitive ratios. We summarize our results below.
Online e-net. We present the first deterministic online algorithm for intervals in R with an optimal competitive ratio of (llo 2). This result is tight, as also establish lower bound of 22 !) for online s-net for intervals. Next, for axis-aligned rectangles in IRZ and boxes in R we devise randomized algorithms with near-optimal competitive ratios of (loo !) and (log" }). respec- tively. We make significant progress on classical g-net in the online regime, for which no prior upper bounds were known.
line geometric algorithms. Due to paucity, we move the proofs of several lemmas, theorems, and pseudo-codes in the Appendix. The missing proofs are marked by x.
2 NOTATION AND PRELIMINARIES
We use Z and + to denote the set of positive integers and positive real numbers, respectively. We
use [ri] represent the set {1, 2, .....,.77 n), where n E Z+. For any R. use fZ to denote the set {3z] E 2}. where E is the set of integers. For any point p E Rd, we use p(x;) to denote the ith coordinate of p. where E [d]. The point p an integer point if for each E [d]. the coordinate p(z;) is an integer. By an object, we refer to compact set in Id having a nonempty interior. Let do.(..) represents the distance under the Loe -oom. Given set system (X, R) and any set Y S X, the projection of R onto Y is defined as the set system: Rly = {Y Or : E R}. The VC-dimension of R. denoted by VC-dim(R)) the size of the largest Y C X for which R/y 2Y.
Definition 1. (E-net) Given a set system (X, R) (also known as range space) consists of a fintt set X and a class R of subsets of X. An e-net N C X such that any range r E R with Ir 2 8 |X] intersects N. In other words, any range that has at least a proportion of the elements of P must also intersect the E-net N.
Theorem 1. (Epsilon-net Theorem) [Haussler & Welzl (1987)] Let R) be set system with VC- VC-dim(R) S d for some constant d, and let E >> 0 be a given parameter. Then there exists an absolute constant Cu >> O such that a random N constructed by picking of X independently with d
probability (ca-( 1 ) log 1 + T|p] log (t)) is an f-net R with probability at least 1- --% 7--
Online s-Net. Let Σ (X, R) be a set system, where X' is universe of points in i2d and R. is a set of ranges defined over X. We assume that X' is fixed in advance and the ranges in R are coming one by one. Let ALG be an algorithm for online E-ner for Σ. The expected competitive ratio of [ALG(O] . where the supremum ALG with respect to Σ = (X, is defined by, p(ALG) sup, OPT(a)
is taken over all input sequences a, OPT(a) (() is the minimum cardinality s-net for and ALG(o) denotes the size of the net produced by ALG for this input. The objective is to design an algorithm that obtains the minimum competitive ratio. If the ALG is randomized algorithm, then we replace ALG(a) by [[ALG(rr] (Borodin& & EI- Yaniv, 1998, Ch. 1).
a-Fat Objects. The notions of famess have been heavily exploited in high- digensiiieniin Geometry and Learning Theory. There cxists several definitions of fatness in the literature due to Alefkhani al. (2023); Chan (2003); De et al. (2024a). We use the most standard definition here which is defined with respect to the aspect ratio of the objects. Let a be an object. For any point x E a,
define (z)
maxyede des (2.8)) The aspect ratio a()) = max(a(z) x E o). An object is
minyeda doc (x.9)
4

---

Published as a conference paper at ICLR 2025
considered an a-fatt objecr if its aspect ratio is at least a. A point with a(c) a()) is defined as a center of the object σ. The minimum (respectively, maximum) distance from the center to the boundary of the object is referred to as the width (respectively, height) of the object. A set S of objects is considered for if there exists a constant 0 < a S such that each object in S is a-fat. Note that for set 8 of fat objects, each object a E S does not need to be convex or connected. For an a-fat object, the value of is invariant under translation, reflection, and scaling, A set S is said to be similarly sized fat objects when the ratio of the largest width of an object in S to the smallest width of an object in S is bounded by fixed constant.
3 ONLINE E-NET
In Section 3.1, we analyze the performance of a simple deterministic algorithm for online e-net of arbitrary intervals, which gives asymptotically tight competitive ratios. Then, in Section 3.2, we analyse the performance of randomized algorithm for online s-net of arbitrary boxes in (2 < 3).
3.1 ONLINE E-NET FOR ARBITRARY INTERVALS
In this section, we consider finite range space (X, R), where X' is a set of points in I. and R is the set of arbitrary intervals. In the online setting, the set X is known in advance, and the adversary introduces the intervals one by at each step. Our objective is to construct E-net M X for (X, R) that hits each E-heavy interval in R.
We present deterministic online algorithm tially, N = 0. At each step, we update the set to hit all the e-heavy intervals observed so far. Here, OPT refers to the optimal g-net produced by an offline algorithm that computes the best possible solution.
which maintains an E-net W. Ini-
Let be interval containing points. We partition the interval into 2 disjoint smaller sub- intervals, each containing at most [n/2] points. Let P3 be a jth sub-interval of a, where j E r. Online algorithm. We can now present our online algorithm ALG. The algorithm maintains a piercing set H. for all intervals that have been part of the input so far. Initially, H 0. Upon the arrival of new interval a, if la < e|X',, then ignore a; else we do the following. If it is already hit by H. ignore a. Otherwise, sort the points of n X in the increasing order, say pı.... : P [onxx] 2
and hit a by the point indexed | and
Add the mente-mee points points to H. For concise description of pseudo-code, see Algorithm 1 in Appendix C.
Since we hit all the E-heavy unhit sets at each step, clearly, ALGO-INTERVAL produces an s-net. We need to prove that the size of the net A produced by ALGO-INTERVAL is at most 2 (log (t) 1) times the size of the offline optimal net OPT.
Theorem (*). For online E-net of arbitrary intervals, there exists a deterministic online algorithm with competitive ratio of 2 (log (2) + 1). for any E E (0, 1]. This result is tight: the competitive ratio of any deterministic online algorithm for this problem is at least log +
3.2 ONLINE S-NET FOR ARBITRARY AXIS-ALIGNED RECTANGLES IN IR2
In this section, we consider a finite range space (X, R). where X' is a set of n points in R,,, and R is the set of axis-aligned rectangles. In the online setup, the points are known in advance, and the rectangles are introduced one by one. Our goal is to construct an e-net N for (X, R) that hit all e-heavy rectangles R. Before describing the online algorithm, we first introduce some crucial ingredients that will play an essential role in designing the algorithm.
Construction of the balanced binary free T. We construct a balanced binary search tree T over the point set X, where X = n. Without loss of generality, assume = 2² for some k E Z The root node at level 0 contains all n points. At each level, the parent node splits into two child nodes, each containing half of the points of its parent. This process continues until each node has fewer than points, resulting in tree of depth O (log (t)). with each Ieaf containing OEEn) points. Construction of a random sample. Let P be a random sample of size O (s log log (t)), where E E (d. 1] for sufficiently large constant C' > 1. The points are drawn uniformly at random from X' with probability of π O log (ox())()) Note that the selection of P and its size is extremely
crucial, as it directly influences the competitive ratio of the algorithm. Connection between the tree and the random sample. Each node v of the tree T is associated with subset X C X' (and similarly, P. C P) containing the points of X (resp. P) stored in the
5

---

Published as a conference paper at ICLR 2025
subtree rooted at A line l, corresponding each internal node divides the point set Xr into two subsets, Ny and Ney, associated with the children 01 and 1/2 of v, respectively. Corresponding to each node v (except root) and it's parent v, lines L,, and l, define the strip S...
Construction of maximal Pu-unhit open rectangles set My. For each node v in strip Su, taining [Pe| points from P. located between lines ly and pparm(())) Without loss of generality, let 4 be the left boundary of Su- We need most three points from P. to create a P-unhit open rectangle M. A triplet of points (a, b, c) defines three sides of a rectangle M: right (a), top (b), and bottom (c), with the left side determined by the line l, (refer figure 2a). If either b is missing, the cor- responding side is extended infinitely (see Figures 2b). If is missing, the right side of M extends until it reaches the right boundary line of the strip 8y (see Figure 2c). For each point Pu. the nearest top-left (b) and bottom-left (c) neighbors define the upper and lower boundaries of the rect- angle. If no such neighbors exist, those sides are extended infinity. This process generates up to [P=l rectangles, where each right side is defined by point from P. (Figure 2d). Rectangles defined solely by the top and/or bottom points (b and/or c) are formed by pairing consecutive points along the y-axis, with the right side extending to the opposite boundary of the strip (Figure 2c). This leads to the construction of [Pel + 1 rectangles. Thus, each strip sy contains up to P/P I + maximal P-unhit rectangles.
From the above description, the number of maximal Pn-unhit open rectangles MM within each strip s is bounded by O(PP)). Since the number of nodes in the tree T is O(2log )) the total number of maximal P-unhit open rectangles across all strips is at most (IP)-
(a)
(b)
(c)
(d)
(c)
Figure 2: (a) A triplet of points (a, b, defines three sides of rectangle M. (b) If either top or bottom point is missing, the corresponding side is extended infinitely. (c) If right point is missing, the right side of M extends until it reaches the right boundary line of the strip. (d) Rectangles defined solely by right side point. (e) Rectangles defined solely by top and/or bottom side point.
Finding a suitable Punun open rectangle. If an E-heavy rectangle a arrives and is not hit by P. let be the highest node of such that associated line ly intersects a. We take the sub-rectangle o', which contains at least 2 points. Next, we extend o' to the right until it hits a point of P. or reaches the opposite boundary of the strip s.- Similarly, we extend it upwards (resp., downwards) until it intersects point of Pe, or treat it as an open rectangle. This extended rectangle contains o' and is included in the set M,,
an
Construction of nefe 2, and 5 is small constant greater than 1. Using the g-net theorem, we can construct was _L-net, denoted as NM. for each M n of size Ow log was). These serve as safety-nets that hit every e-heavy input rectangle a that intersects the strip 8, but not hit by P.
For each node of T and each rectangle M E M,, define the weight
wM *|MnX where
The final g-net N for (X, R.) is the union of P with the safety-nets NA for all M. Now, we have all the necessary ingredients to describe the algorithm.
Online algorithm. Let P C X' be a random sample of size O (e log log (t)). . In addition to P, the algorithm also maintains a safety-net SN, with N = P SN. Initially, 1, P, and SN are empty. For each new rectangle a presented, update I = I a. If a contains any point from P, then we are done. If not, check whether intersects any point from the current safety-net SN. it does, no further action is needed. Otherwise, find the highest node v in the tree T where the associated line 1, intersects σ. Identify a sub-rectangle o' S a containing at least en 2 points, then extend o' to form a Pu-unhit rectangle M. Finally, add all points from the --net NM to the safety-net SN. For a concise description of the pseudo-code, see Algorithm 2 in Appendix C.
Readers familiar with the technique of Aronov et al. (2009) will recognize the similarities between our approach and theirs. However, the key distinctions in our algorithm lie a different selection of the random sample, different weight assigned to each constructed rectangle M E M, and consequently, the size of the resulting online E-nct changes.

---

Published as a conference paper at ICLR 2025
Correctness. Note that N consists of random sample P C X' along with war-net for each M E M. Let a be a E-heavy rectangle. If the input rectangle a is hit by P. we are done. If a does not contains any point from P. then we will show that will be hit by point from the safety-net NM, corresponding to some PPuunhit open rectangle M. Recall that if an E-heavy rectangle a arrives and is not hit by P, we consider the highest node of T such that the associated line l, intersects o. We take the sub-rectangle o', which contains more than half points of a. Next, we find the maximal Po-unhit open rectangle M E M, such that o' is completely contained in M. Also, recall that the weight of every M was WM- = =MMn where s = 26 Due to E-net theorem, for any M E M,
we can construct 1/war-net NM for M. Note that definition of e-net that NM hits o'.
I M
En/2 mw
2
Hence, due to the wM
Theorem 3. For the online E-net problem with arbitrry axis-aligned rectangles, there exists an algorithm with an expected competitive ratio of at most O (log (1)). Here, e E 1J. where C is sufficiently large constant.
Proof. Now, we will show that the expected competitive ratio of the algorithm is O (log (2)). Let I be the collection of all input rectangles arrived one by one to the algorithm. First, we will compute how many points are placed by our algorithm for the input sequence I. Let N and OPT be the epsilon-net constructed by our online algorithm and best offline optimum for input sequence I. Recall that the net N constructed by our algorithm is the union of p and wer-net for all M M, where M is the collection of all P-unit open rectangles. Now, we consider
[[] =BiPP| + Σ Σ
(was log WM)] & B||P"1| + [[[ log wM)l
ET MEM,
=B||P']] + (wMr log uM E MM < ((
[E|PP
WM log WMs
(Since, B[M dominates over B[(P"))
-0 01108 log log ( x (wM log
=0 (
01og log log -
(6 )
log -
(Since, was (s) and 26
Due to Pach & Tardos (2011), for (X, where X is a finite set of points, and R consists of axis-aligned rectangles, the size of the smallest g-net (for E (0, 1)) is at least s(} log log L). Thus, the offline optimal OPT for any input sequence I will have size at least (( log log ! )))
So, the expected competitive ratio of the algorithm will be B[|N OPT
olloglog log( (t) ())x(())))))))) (()) log(2)))
o((:) log log )))
O (log (t)). Hence, the theorem follows.
Since we using the Pach & Tardos (2011) result as lower bound, the claimed upper bounds are not instance-optimal. Achieving instance-optimal bounds would require an online lower bound for these objects. To the best of our knowledge, such a result has not yet been established in the literature, making it an intriguing open problem.
3.2.1 EXTENSION TO HIGHER DIMENSIONS.
Our approach can be extended from R² to RR3 We begin by selecting random sample P S X' in R3 of size O (e log log t), similar to the case in R² Then, we construct a three-level range tree T over the points of X' using standard methods from Computational Geometry (see Berg et al. (2008)).
This three-level range tree will help in construction of at most O (IP)-- logg !) many safety-nets. (For the complete construction see Appendix A.2). Thus, we have the following theorem.
Theorem 4 (*). For the online s-net problem with arbitrary axis-aligned boxes in R.3, there exists an algorithm with expected competitive ratio of at most O (log" (2)). Here, E 11, where C' is a sufficiently large constant.
Remark 1. For dimensions d i the number of maximal P-unhit open orthants within each octant containing k points from P may no longer be linear in k. In fact, it can grow as @(kl4/2)), which at least quadratic for 2 4 (see Kaplan et al. (2008)). This contrasts with instances I or RR3 where the number of such maximal unhit boxes is linear in k2 allowing us to efficiently bound the net size, which results in a small net size and a favorable competitive ratio. However, due to the potentially non-linear growth in higher dimensions, it is unclear whether the tree construction algorithm used to find a small E-net will yield similarly efficient results for d 2 4.
7

---

Published as a conference paper at ICLR 2025
4 ONLINE PIERCING SET PROBLEM
In this section, we study the online piercing set problem for various families of geometric objects. In Section 4.1 and 4.2, we analyze the performance of simple deterministic algorithm AL.G- AL.GO-CENTER for piercing axis-aligned boxes and ellipsoids in R respectively, which gives the desired competi- tive ratios. Then, in Section 4.3, we analyse the performance of a deterministic algorithm ALGO-FAT for piercing fat objects in IR...
In what follows, we first describe a simple deterministic algorithm.
Let ' be the piercing set maintained by our algorithm to pierce the incoming object. Initially, N = 0. Our algorithm does the following on receiving new imput object a. If the existing piercing set pierces do nothing. Otherwise, our online algorithm adds the center of a to N.
Online algorithm:
The analysis of the algorithm is similar in nature for fat objects, axis-aligned boxes and ellipsoids in Rdd. To bound the competitive ratio, we determine the number of points placed by algorithm against each point p in an offline optimum. To compute the number of piercing points placed by our algorithm, we consider the region containing all objects that can be pierced by the point p. We have partitioned this region into Olog M) regions such that our algorithm places the same number of piercing points in each of these regions. Finally, we give an upper bound on the total number of points placed by our algorithm in each of these regions. The competitive ratio is Ollog M) multiplied by this number. Proofs not included in the main body of this section are presented in Appendix B.
4.1 ONLINE PIERCING FOR AXIS ALIGNED BOXES IN Rdd
In this section, we study the piercing set problem for (X' R)) where the set X' is the entire Id and R is a family of axis-aligned arbitrary boxes from [1, NJá having side lengths in [1, MJ. Note that boxes can have arbitrary aspect ratios, thus they are not necessarily fat objects. Hence, the result for piercing a-fat objects (De al. (2024b)) does not apply to boxes in RRd In fact, surprisingly, no online algorithm is known date even for rectangles in R². For fixed d E Zt. for piercing axis- aligned boxes in Rd, we propose a simple deterministic algorithm ALGO-CENTER competitive ratio O(log M)) (Theorem 6). There exists randomized lower bound for hypercubes in of 2(log M) (De et al. (2024b)), which also holds for axis-aligned rectangles in Rd Thus, the competitive ratio obtained by our algorithm is asymptotically tight.
CENTER which obtains a
In this section, we first present the analysis of ALGO-CENTER for rectangles in IR2. Later, we gen- eralize it for higher dimensions (see 4. 4.1. Throughout the section, all distances are Too distances, and all boxes are axis- axis-aligned, unless stated otherwise.
Theorem 5. For piercing axis cris-aligned rectangles in IR? having the length of each side in the range [L, M), ALGO-CENTER has competitive ratio of most O(log M). ).
Proof. Let I be the set of rectangles presented to the online algorithm. Let '' and OPT denote the piercing set returned by the online algorithm ALGO-CENTER and an offline optimal for I. Consider point p OPT and let I" C I be the collection of all the rectangles arrived far and contain the point p. Let A C N be the set of piercing points placed by ALGO-CENTER to pierce all the input rectangles in IP. Clearly, we have N = U UPEOPT Np. Consequently, the competitive ratio of our algorithm is upper bounded by maxpEOPT INP).
Now, consider any point E No. Since is the center of rectangle E I that contains the point p and has a side length of at most M, the distance between a and p is at most 2 As a result, square S of side length M, centered at p. will contain all the points in N², Next, partition the square into (llog MJ + 1) smaller nested squares. For E ([log M + 1)), ,, let S, be a square with sides of length M - Define the annular region A, = S S.+1, where E [ol MJ + 1)]. Notice that
the annular region A; contains all the rectangles of I, whose length of both the sides are at least M
T Let N?? = A/P n A; be the subset of N that is contained in the region A,.
Lemma 1 (+). INP < 12.
Since UNT N₂ and due Lemma we have A/ < 12, therefore [Np $ x2x (llog M +1) Ollog M). Hence, the theorem follows.
8

---

Published as a conference paper at ICLR 2025
4.1.1 GENERALIZATION HIGHER DIMENSIONAL BOXES
Similar to R², we have hypercube H of side length M centered at E OPT, containing all the centers of the objects Zy. We can partition the hypercube H into log M smaller hypercubes S. Specifically, the hypercube S; has all sides of length M 2 Similar to the two dimensional case, here also define the annular region A, S; \ S1+1. where E [[[log M + 1)]. Notice that the annular region A, contains all the boxes of Zp such that the length of all the sides are at least M Let N? = A n A, be the subset of . that is contained in the region A,, For each i [(Llog M [+1]], we show that [N? s -1) = O(4") (due to Lemma 2). Since UN? = Ng-- Thus, have the following theorem.
Theorem 6 (+). For fixed d E z², for piercing arbitrary box in R having the length of each side in M), ALGO-CENTER has a competitive ratio of most Olog M).
4.2 ONLINE PIERCING FOR ELLIPSOID IN Rd
In this section, study the piercing set problem for family of ellipsoids having length of axis- aligned semi- semi-major and semi-minor axes in [1, M]. where M > 1. Similar to rectangles, ellipses can also have arbitrary aspect ratios and are not assumed to be fat. Surprisingly, known to date, even for ellipses in R²2 In this section, for fixed d E z+, we show that for piercing ellipsoids in Rd, ALGO-CENTER achieves competitive ratio of at most Ollog M) (Theorem 8). The competitive ratio obtained by our algorithm is asymptotically tight, due to lower bound of De al. (2024a) for ball (loog M).
online algorithm is
Here, we first present the analysis of the algorithm for the case of ellipses in IR2 Later, in Section 4.2.1, we generalize the analysis of the algorithm for the higher dimensional ellipsoids (see 4.2.1). The proof of the following theorem is similar to the proof of Theorem 6.
(a)
(b)
Figure 3: (a) Partitioning the disk D of radius using circular sector C(0,r); ; (b) Description of circular sector C(O, r:) and circular block Ci,..
Theorem 7 (+). For piercing ellipses in R² having length of axis aligned semi-major and semi- minor axis in the range [1, M), AL.GO-CENTER achieves a competitive ratio of at most O(log M).
4.2. GENERALIZATION TO HIGHER DIMENSIONAL ELLIPSOIDS
Similar to the wwo-dimensional case, we construct a d-dimensional ball B of radius M centered at p OPT, containing all the centers of the d-dimensional ellipsoids in Ip. We can partition the d- dimensional ball B into [log M + smaller concentric d-dimensional balls B;. Specifically, the d- dimensional ball ball B, has radius _ Similar to the two dimensional case, here also we define the annular region A, B, B,+1, where E [[[log M [[]]] Notice that the annular region A, contains all the d-dimensional ellipsoids of I, such that the length of all the principal semi-axes is at least
We prove that for each i e [[[log M + 1)]. we have !NT ((1+ sin(9/2)
d -1) where
2
0 = cos have the following theorem.
14V1+442 and x = v5-1, Since UN? = N2- Thus, similar to Theorem 7, we
Theorem 8 (x). For fixed d E 2+, for piercing d-dimensional ellipsoids having the length of all the axis-aligned principal semi-axes in M),, ALGO-CENTER has a competitive ratio of at most Olog M).
4.3 ONLINE PIERCING FOR Q-FAT OBJECTS d
In this section, we focus on piercing a-fat objects Rd. Currently, the best known bound on competitive ratio is O ((2 2) log M) (De et al. (2024a)). We improve this result for (a

---

Published as a conference paper at ICLR 2025
2 1] by introducing simple deterministic algorithm with slightly better competitive ratio of O ((2 log M). This resolves an open problem posed by De al. (2024a), which seeks to narrow the gap between the lower and upper bounds for piercing a-fat objects in higher dimensions. We consider all the distances in this section be under -norm, unless stated otherwise.
Before describing the algorithm, we first present some essential ingredients that will be used for describing the algorithm. For any 2[ M ]] U {0), let E 2.2 and uj 3.2 if is even, and b = 3.2 +1 and = 4.2 1=1 +1 if j is odd.
Layer of the objects. We partition the set of all similarly-sized fät objects into [2 [loo M + + {0} layers. When j is even (respectively, odd), the layer Lg contains the fat objects having widths in 1gz
Lattice. Let IT's = (arlςer + 02l +... + aalsed (0), 02,.... ad) E zd) be d-dimensional lattice spanned by the standard unit vectors. To visualize I1, IP2 and IT we refer to Figure 4.
P.
Pr
1
E
P-g
(b)
(0)
Figure 4: The points of II are drawn (a) for d 1, (b) for 2, (c) for d (c), projections of planes Pt,. Po and P-e, rectangular region is depicted. Here, for any k E R, Pv ty R2d v(xa) } is hyper-plane.
Now, we present simple deterministic online algorithm for piercing fat objects in R4.
Online algorithm ALGO--ATT Let / be the piercing set maintained by our algorithm to pierce the incoming fat objects. Initially, A 0. On receiving new input object with width following. If it already hit by N, then ignore a. Otherwise, first determine the layer Ly in which a belongs, where j = logg s. Then, our algorithm choose the closest point from II n a. and adds r to H.
do the
For the correctness, efficient implementation and analysis of the online algorithm, see Appendix B.3.
Theorem 9 (+). For piercing similarly-sized fat objects with widths M), ALGO-FAT has a competitive ratio of at most O + 3 [1d loo M).
5 CONCLUSION
We studied the online e-net and online piercing sel problems for wide range of geometric objects. For the online e-net, we have obtained asymptotically tight bounds for the competitive ratios for some of these objects. Two future directions particularly arise from our work. What happens to other geometric objects? We believe that some techniques used in this work could be extended to other related geometric objects of constant description complexity Rd for < 3. Obtaining tight bounds for all objects of bounded VC-dimension is interesting open problem. Moreover, to ensure the cardinality of an optimal sample size, we used the value of & within certain regime. Designing online algorithms for any > 0 is interesting open problem. For online piercing ser, we have established asymptotically tight bounds on the competitive ratios for piercing hyper- rectangles and ellipsoids in Rd for any d N. A challenging open question remains whether it is possible to remove the dependence on the dimension from the competitive ratios bound for classes of objects of bounded VC-dimension.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Pankaj K. Agarwal, Sariel Har-Peled, Rahul Raychaudhury, and Stavros Sintos. Fast approximation algorithms for piereing boxes by points. Proceedings the ACM-SIAM Symposium on Discrete Algorithms, SODA. SIAM, 2024. doi: 10.
URL https: //tp::///ol /doi.
org/10.1137/1.
1137/1 9781 978111197792.1111
Shanli Alefkhani, Nima Khodaveisi, and Mathieu Mari. Online hitting set of d-dimensional fat ob- jects. In Apprximmation and Online Algorithms, pp. 134-144. Springer Nature Switzerland, 2023. ISBN 978-3-031-49815-2 URL https: //t::///doiiie orw//0. 1007 978 031 49815-22222 2_ 10.
Noga Alon. A non-linear lower bound for planar epsilon-nets. Discrete Comput. Geom., 27(2)235-244, March 2012. ISSN 0179-5376. URL https: /ooi orgg orgg10.10077 $0C454-010-9323-7
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM J. Comput., 39(2):311-370, 2009, doi: 00.1377000661946 URL https:
//doi. www. 10. 1137/06066194
Boris Aronov, Esther Ezra, and Micha Shair. Small-size s-nets for axis-parallel rectangles and boxes. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pp. 639 648. Association for Computing Machinery, 2009. ISBN 9781605585062. doi:
10..0.114115555 10.1145/1536414.1 1536500.. URL https: /doi...... 1ttp://...........111111144..... 15365001
Maria-Flowe Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complex- ity active learning. Machine learning, 80:111-139, 2010. URL httpp:://dat /ttp:://///o..o//..... org/10.
1007 2007/s10994 010-5174-1
Boaz Ben-Moshe, Matthew J. Katz, and Michael Segal. Obnoxious facility location: Complete service with minimal harm. International Journal of Computational Geometry & Applications,
10(06):581-592, 2000. doi: (04422/022181159000000000
URL attpps://ool org/ /10.
Mark de Berg, Otfried Cheong, Mare van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer- TELOS, 3rd ed. edition, 2008. ISBN 3540779736.
URL https: / /www.wwwoo.ooooooooooo//t worlddate wtt.///atttoooo/////////////////
Sujoy Bhore and Timothy M. Chan. Fast static and dynamic approximation algorithms for geometric optimization problems: Piercing, independent set, vertex cover, and matching. In Proceedings of the ACM-SIAM Symposium Discrete Algorithms, SODA. SIAM, 2025.
Allan Borodin and Ran El-Yaniv Online computation and competitive analysis. Cambridge Uni- versity Press, 1998. ISBN 978-0-521-56392-5. URL https:// https::/cbll..rrggg https///ddll..orrreeebbbkkk httpg///cc////////////////
daglib/ 000/009901333
Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178-189, 2003. doi: 001006//90196-7774220004444 URL https://
doi. http://10..111111-1-11 6774 (02) 00294-8.
Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. SIAM J. Compur., 3316):1417-1440, 2004. doi: 10.1137/
S00975397024188499 URL https:// http:///.....o......../////3////
Kenneth L. Clarkson and Kasturi Varadarajan. Improved approximation algorithms for geometric set cover. In Proceedings of the Twenty- Annual Symposium on Computational Geometry, SCG '05, pp. 135-141. Association for Computing Machinery, 2005. ISBN 1581 139918. doi: 10.1 10.1145/1064092.100 10641 URL https:/// /tt:://dooii org/10 / 64 022 1064101.11111111 1051
Kenneth L. Clarkson and Kasturi R. Varadarajan. Improved approximation algorithms for ge- ometric set cover. Discrete & Computational Geometry, 37(1):33-5, 2007. doi: 10.1007/ s00454-006- 1273-8.
URL htt.s: httppps::///..../ /ttp://///oooo..00100/////////// o:tp:/100000000000000-00---12120
11

---

Published as a conference paper at ICLR 2025
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the pres- ence of adversaries. Advances in Neural Information Processing Systems, 31, 2018.
URL https://proceeee hwwpeeiiiiinnnnnuneeeeeeeee 8 8f85517967795ees wwwfff6678 0at.5179877755666666666888828
Abstractt html.
Minati De and Satyam Singh. Online hitting of unit balls and hypercubes in R using points from zd Theoretical Computer Science, pp. 114452, 2024. ISSN 0304-3975. doi: https://doi.
URL https::///// //w::///wwwwwo. wwt.://ciecceiiee....... com/ samnncceeee////
arriclee/s11/3334975550000
Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh. Online geometric covering
and piercing. Algorithmica, 86(9):7739 2024a. doi: 10.1007/00055--24--02244 URL
https: //ooi:///di.../ www.oogg.....oo http://11..1000000000000 http:////.aa...r......000/555550 001144433022-----12111
Minati De, Ratnadip Mandal, and Satyam Singh. New lower bound and algorithms for on-
line geometric hitting set problem. arXiv preprint 1111v:2409.11166. 2024b. URL https:
//aaxiv. org/ awwpaa/....////// 11166..
Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recogni- tion, volume 31 of Stochastic Modelling and Applied Probability. Springer, 1996. ISBN 978- 1-4612-6877-2. doi: 978-1-4612-00 01122-071-33
0t00//9781--412-071-111 URL https:://ai.org//D////
Adrian Dumitrescu and Csaba D. Tóth. Online unit clustering and unit covering in higher dimen- sions. Algorithmicu, 2022. doi: 10.1007/000453-02-000000
URL https: http://oooooooooooooooooooo org/
20.10077/00453-0211
Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth. Online unit covering in Euclidean space. Theor Comput. Sci., 809:218-230, 2020. doi: 10. 10.1016f..es.2019.1222 URL https:///ooii
org/10..0.. 1.0.10066 6/ tcs. 2019. 11199.12. 12 010.
Alon Efrat, Matthew J. Katz, Frank Nielsen, and Micha Sharir. Dynamic data structures for fat ob-
jects and their applications. Comput. Geom., 15(4)) 227, 2000. doi: 10. 101111/00925-77119999 00059-0. URL https: :ttttps::///e/ http://coiooooo http://///o.....././///oe////t.e
0000225566002--000 7721 (99) 00059-0.
Guy Even and Shakhar Smorodinsky. Hitting sets online and unique-max coloring. Discret. Appl. Math., 178:71-82, 2014. doi: 1016/j dam. 2014. 019.
URL htttps://do..rgg///
M. R. Garey and David S. Johnson. Computers and Intractability: Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7. URL http:/ /dblp.
uni-trier. sii-trier.de/rac recree///e/eeeeeeee////ee//eeeee balee//bb//e bibbbbbbbbooooee fm/GareyJ79.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn, Res., 16: 3487-3602, 2015, doi: 10.555/278822222122111 URL https:://// att.://mmmo///ooii....ooooooooo. 5555 2912111.
David Haussler and Emo Welzi. 8-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. URL htt.tttt///aaat semant iemanttcscholaan ascholar. ooroolrrrr...rooooooooooooo CorpusTD: 27638326.
Hai Huang, Andréa W. Richa, and Michael Segal. Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks. Mob. Networks Appl., 151: 161, 2004. doi: 10. 2tB.://.MMM.....000066666666..6 1023/22 MONE. 000000013220 53247. lcc
URL https:
Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin. Efficient colored orthogonal range counting. SIAM Journal on Computing, 38(3):982-1011 2008 doi: 10.1137/070684488. URI.
https:/ //ooi 0rg/10.10 00.11107706644888
Matthew J. Katz, Frank Nielsen, and Michael Segal. Maintenance of piercing set for intervals with applications. Algorithmica, 36(1):59-73, 2003. doi: 10. 10.11007::00453-002000000 URL
https:/ http://///o...r/1...1.11. 1000700..1000000 00000000/0033-30
12

---

Published as a conference paper at ICLR 2025
Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese. Online and dynamic algorithms for geometric set cover and hitting set. In 39th International Symposium on Computational Geometry, SoCG 2023, volume 258 of LIPIcs, pp. 16::1117..... Schloss Dagstuhl -Leibniz-7eentrum für Informatik, 2023. doi: 10.42000.PCCS555000223..444 .eddiiorg// 00. 1/300/IIPICS. SoCG. 2023.44.. 446.
URL https:
Mark J van der Laan, Sandrine Dudoit, and Aad W van der Vaart. The cross-validated adaptive epsilon-net estimator. Statistics & Decisions, 24(3):373-395 2006.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. stat, 1050(9), 2017. URL https: / //doi. org/ 10. 4 48550/arX21. 1766. 06083.
Jifí Matoušek, Raimund Seidel, and E. Welzl. How to net lot with little: small e-nets for disks and halfspaces. In Proceedings of the Sixth Annual Symposium on Computational Geometry, SCG '90, pp. 16-22. Association for Computing Machinery, 1990. ISBN 0897913620. doi: 10.1145/98524.985500 URL httpt::/dddd. /ttp://i...r/11.115/////883 98524.98530.
Jifí Matoušek. Reporting points in halfspaces. Computational Geometry, 2(3):169-186, 1992.
ISSN 0925-7721. doi: http:///d.ooggooo.../////22/2220 URL https: htop:://wwn
sciencedirect htmm//ccinceeeeeeem http:///mnn/aaaaccceee//////22//
Omar Montasser, Steve Hanneke, and Nathan Srebro. Veclasses are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pp. 2512-2530. PMLR, 2019. URL
httt:://proceete
Nabil H Mustafa. Sampling in combinatorial and geometric set systems, volume 265. American Mathematical Society, 2022.
ott.://r..........o.uuu......... surv-265.
János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. In Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pp. 458- 463. ACM, 2011. doi: 10.11457/9981966.19977.. URL
1998196 111.8196.199989 1998271.
János Pach and Gerhard Woeginger. Some new bounds for epsilon-nets. In Proceedings of the Sixth Annual Symposium on Computational Geometry, SCG '90, pp. 10-15, New York, NY, USA, 1990. Association for Computing Machinery. ISBN 0897913620. doi: 10.1145/98524.98529. URL https:t///// doi weopi.orgg11..0 11....111999888 98529.
Micha Sharir and Emo Welzl. Rectilinear and polygonal p-piercing and p-center problems. Pro- ceedings of the 12th Annual Symposium Computational Geometry (SoCG), pp. 122-132, 1996. doi: 00.114//27228822272222
URL https:/ /tt::///ooiio /ttp:/oo..o.....o///oo///// 1111111122211 0111221882372585 237255.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-28) 1971. doi: 10.1137/11101 116025. URL https:/ /doi wwwploorg/111....
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
13

---

Published as a conference paper at ICLR 2025
A MISSING PROOFS OF SECTION 3
A.1 MISSING PROOFS OF SECTION 3.1
Theorem 2. For online E-net of arbitrary intervals, there exists a deterministic online algorithm with a competitive ratio of 2 (log (e) 1). f any E E (0. 1]. This result tight: the competitive ratio of any deterministic online algorithm for this problem is at least log +
Proof. Upper Bound. Let I be a collection of intervals presented to the online algorithm. Let S C
be the collection of intervals (a, b] such that [[a, bj n X 2 s| For each i [[lgg 11 U {0), let S; be the collection of intervals [x, y in S such that [[a, y] nx E 2(+ Let !V and OPT denote the sub-collection of e-nets returned by the online algorithm and an optimal offline
algorithm, respectively, for S. Let p be point in OPT. Let S(p) C S be the set of intervals that
contains the point p. For each i E [ogg 21] U (O),, let ((()) = S(p) n, Let (G()) C be the hit an input interval in Sp(p) which not hit.
set of points that are placed by the online algorithm We claim that our online algorithm places at most 2 points for all intervals in (,)) Without loss of generality, let us assume that a E (p) the first input interval that not hit upon its arrival. In order hit o, our online algorithm adds the points indexed
lenx| 2
and
|anx
to (sp)).) Notice
that we can partition a into two disjoint sub-intervals Pd and Pa such that they contain |
lanx' and
points, respectively. Let P1 contains the point p, where E (l,r). Let o' 0) E (p)))
2
be any interval. Observe that, IPa <
lonx]
< 2'E|X\. Also, by definition, of E (p) contains
at least 2'e|X(] points, and a' n Pd + 0. As result, o' hit by either the point of a indexed lonx|
or Lonxx
Therefore, our algorithm does not add any point to (p) for o'. Thus, ((p) contains
at most (flog2 11 + 1) points.
Lower Bound. To prove the lower bound, we can think it as a game between the adaptive adversary and online algorithm. Let 0 be the first interval containing all the points presented by the adver- sary to the online algorithm. Let P1 be a point placed by the online algorithm to pierce the interval 01. The point P1 partitions the interval 01 into two parts, of which, let of be a part containing least 2 points that does not contain the point P1. Now, the adversary can present an interval 02 S of containing exactly 5 points. For the new interval a2 any online algorithm needs new piercing point P2. Now again, one can define a partition of of a2 depending on the position of the point P2 such that of contains at least points and does not contain Ps. The adversary will present an interval 33 C cof containing exactly points. In this way, the adversary can adaptively construct log 1 + intervals (last interval containing en points) for which any online algorithm needs log + distinct points to pierce, while an offline optimum needs only one point. Hence, the lower bound of the competitive ratio is log _ 1.
Hence, we conclude the proof of the theorem.
A.2 MISSING PROOFS OF SECTION 3.2
Theorem 4. For the online e-net problem with arbitrary axis-aligned boxes in R.3, there exists an algorithm with an expected competitive ratio of at most O (log" (t)). Here, E (). where C a sufficiently large constant.
Before presenting the proof of the theorem, first define some important ingredients that will play an essential role in proving the above- mentioned theorem.
We begin by selecting random sample P C X in R3 of size O (e log log }). similar to the case in R Then, we construct a three-level range tree T over the points of X. This can be obtained by fol- lowing standard methods from Computational Geometry (see Berg et al. (2008)). The construction of the range tree proceeds as follows: in the primary tree, the points sorted by their z-coordinates,
14

---

Published as a conference paper at ICLR 2025
in the secondary tree by their g-coordinates, and in the tertiary tree by their 2-coordinates. Each node u in the primary tree 7 is associated with a subset R2 C X' and a secondary tree Tu on this subset. Each node in Tu is similarly associated with subset R. Rw, and tertiary tree Tu this subset. Finally, each node w in a tertiary tree Tu corresponds to a subset Ru,,,,r C Ru,..-
For each internal node in the primary tree, associate plane hu orthogonal the r-axis that splits the points into subsets and stored at its children (analogous to the line l, for each node u). Similarly, for each node in Tu and each node w in Tu, associate planes he, and 0,,0, orthogonal to the y-axis and z-axis, respectively. Trees of each level has depth of at most Olog !), and the total number of nodes in the range tree 7 is O ( log" 4
These orthogonal planes define octants Su,n,a for each node w of the tertiary tree, analogous to the strips in the R² For each octant, we construct a set set Mu,,,, of maximal P-unhit boxes. Each box M requires at most three points from Pu.r. define its boundaries on each distinct facets. Similar to the case in IR2 the number of maximal boxes [Ma,,wel the total number of maximal boxes across all octants is not more than O (1 log" ă IPI)-
most [P u,,, +1 ((P)). Therefore,
To handle an input box that is e-heavy but not hit by P, we follow a similar procedure like the R2: Identify the lowest-level plane intersecting a, extend a to the boundary of the octant or until intersects point from P. Pu,n,uu and form a box that belongs to the set Mu,.,w. Finally, we define weights WM for each M E .Mu and construct safety nets NM as in the planar case. The final g-net in I3 is the union of with all the safety nets Nus. Using the similar reasoning described in Section 3.2, it is possible to show that the constructed set N is indeed an e-net, where E 11/C,1) for any sufficiently large constant > Now, the proof of Theorem is as follows.
Proof. The expected size of N is given as, B]] = E
PP' + EBET EVET, EwET... EMEM...... War log wM]. which can be bounded as E'|P'|| + O (PP) 1 log" !)) WM log W..
Finally, applying the lower bound results from Pach & Tardos (2011), one can establish that the competitive ratio for the RR3 case is:
O (log" log log 1 x 0 log !)) =0 (108") !
JOPT
0 log log
This shows that the competitive ratio is O (log" 3 :).
B MISSING PROOFS OF SECTION 4
B.1 MISSING PROOFS OF SECTION 4.1
Lemma 1. [N 12.
Proof. Since A; = S; \ S5+1. the distance (under Tr norm) from the center to the boundary of A5 as respectively. Thus, the annular region A; can contain squares of side S; and S;+1 is 21-1 and M length 2-FT-
Claim 1. The annular region A, is the union of at most 12 disjoint squares, each having side length Ad
Proof. To calculate the number of such squares of side length 2 in the annular region A,, we need to find the ratio of area of A, with respect to the area of square S. The area of A, is equals to the area of S, minus the area of S Thus, the area of A, is 3M2 The area of S 2 16
M
Thus the
ratio will be 12. Hence, the claim follows.
Li
To complete the proof, next, we argue that our online algorithm places at the most one piercing point in each of these squares pierce the objects in I", Let S be any such square of side length (2)
15

---

Published as a conference paper at ICLR 2025
and let 91 S be a piercing point placed by online algorithm. For contradiction, let assume that our online algorithm places another piereing point Q2 E H, where Q2 is the center of an object Ip- Since a contains both the points p and 92. the distance (under Loc norm) between them is at least M Note that the distance (under Lo norm) between any two points in S is most 2 as a result, a already pierced by (1, since a a rectangle of side length at least 27. This contradicts our algorithm. Thus, the region contains at most one piercing point of AV.. Hence, the lemma follows.
M
2'1
Lemma 2. W!! S (2 1) 0
Proof. Since = S \ S1+1. the distance (under Lo norm) from the center p to the boundary of S, and S is 2 and 2 respectively. Thus, the annular region A; can contain squares of side M length 2-II-
Claim 2. The annular region As is the union of at most 12 disjoint squares, each having side length
Proof. To calculate the number of such hypercubes H of side length M in the annular region AG, we need to find the ratio of the volume of A; with respect to the volume of hypercube S. The area of A equals to the volume of St minus the volume of Si+1. Thus, the area of A; is 12a-1) M² The area of S is Ta. Thus the ratio will be 2d 1). Hence, the claim follows.
2
To complete the proof, next, we argue that our online algorithm places at the most one piercing point in each of these squares to pierce the objects in TP. Let S be any such square of side length (2)++T, as
and let QI S be a piercing point placed by online algorithm. For contradiction, let assume that our online algorithm places another piercing point E H, where Q2 is the center of an object Ip- Since a contains both the points p and q2, the distance (under Loe norm) between them is least 21 Note that the distance (under Loo norm) between any two points S is most _M as a result, o is already pierced by Q1. since a a rectangle of side length at least M This contradicts our algorithm. Thus, the region contains at most one piercing point of A,.. Hence, the lemma follows.
2
B.2 MISSING PROOFS OF SECTION 4.2
Theorem 7. For piercing ellipses in I² having length of axis aligned semi-major and semi-minor axis in the range [1, M), ALGO-CENTER achieves a competitive ratio of at most O(log M).
Proof. Let I be the set of input ellipses in IR2 presented to the algorithm. Let N and OPT be two piereing sets for returned by ALGO-CENTER and the offline optimal, respectively. Let p be any piercing point of the offline optimal OPT. Let Ip C I be the set of input ellipses pierced by the point p. Let N2 be the set of piercing points placed by our algorithm to pierce all the ellipses in Ip- To prove the theorem, will give upper bound of [Ngl-
Let us consider any point a E Np. Since a is the center of an ellipse a E Ip (containing the point p) having length of semi-minor and semi-major axes at most M, the distance between a and is at most M 2. Therefore, a disk D of radius M, centered at contains all the points in Np. Let v5-1 be a positive constant. Let Dj a disk centered at p having radius r; (I+=)=-+ where i [[[log M + 1)]. Note that Dj. Dz...., Dm are concentric disks, centered at p. Let 1
0 cos ( 1+v3) be a constant angle in (0, lll- Similar to the case of rectangles, now we define the annular region A, = D; D:-1. Let C(O,r;) r:) be a circular sector obtained by taking the portion of the disk D, by a conical boundary with the apex at the center p of the disk and 0 as the half of the cone angle (for an illustration see Figure 3a). For any i E [|og M + 1). let us define the ith circular block C, C(0, rx) \ C(A, r++1) (for illustration see Figure 3b). Notice that all the ith circular blocks contain all the ellipses of I, having length of both the meji-major and semi-minor axes at least r,,
16

---

Published as a conference paper at ICLR 2025
Similar to Lemma 1, we have the following lemma.
Lemma 3. [A]" < 7-
Proof. Notice that the total angle of any disk D centered p is 2T. If any cone having apex p and angle 20, then at most [ cones will cover the entire D. Thus, it is easy to observe that 2x
2#
circular blocks will entirely cover A, there are at most / circular blocks Cs.e in A, Now, we will show that in each circular block our algorithm places only one point. Let 91 be the first piercing point placed by A1GO-CEENTE in Ci,o- For contradiction, let us assume that ALGO--ENNTE places another piercing point Q2 Ci.o. where Q2 is center of some ellipse and 42. and the distance between them is at least rę. Note that the maximum distance between any two points in Ci,0 is at most max o It is easy to observe that max on is at most 7;- As result, is already pierced by Q1- This contradicts that our algorithm places two piercing points in Cr,o- Hence, ALGO-CENTER places at most one piercing point in the circular block Ci to pierce an ellipse in Ip. Hence, the lemma follows.
Ip. Since contains points
Since UAT N2 and due to Lemma 3 we have [W? S T therefore [V₂] S S llg MJ+1) O(log M). Hence, the theorem follows.
Theorem 8. For fixed d Zt, for piercing d-dimensional ellipsoids having the length of all the axis-aligned principal semi-axes in M), ALGO-CENTER has a competitive ratio of at most Ollog M).
Proof. Let Z be the set of input ellipsoids in I2d presented to the algorithm. Let and OPT be two piercing sets for I returned by ALGO-CENTER and the offline optimal, respectively. Let p be any piercing point of the offline optimal OPT. Let Ip S be the set of input ellipsoids pierced by the point p. Let NVp be the set of piercing points placed by our algorithm to pierce all the ellipsoids in Ip. To prove the theorem, we will give an upper bound of [Wyl--
Let consider any point the point p) having length of principal semi-axes is at most M, the distance between a and p is most A7 Therefore, ball B of radius M, centered at p, contains all the points in NVp- Let
Np. Since is the center of ellipsoids
Ip (containing
= 1/-1 be positive constant. Let D; be disk centered at having radius r, (1+2)'TT where i E [[[log M + 1)]. Note that D1, D2..... Dm are concentric balls, centered at p. Let 0 1 cos
M
-41=)) be a constant angle (0, fol- Similar the case of rectangles, now we define the annular region A; = D; D.-1. Let H (0, r:) be hyper-spherical sector obtained by taking the portion of the ball B, by a conical boundary with the apex at the center of the ball and as the half of the cone angle. For any i [[log M] 1), let us define the ith hyper-spherical block
H. (0, ) H(,, 1). Notice that all the ith hyper-spherical blocks contain all the ellipsoids least rí.
of I, having length of all the principal semi-axes
sin(0/2)) (i)+))))/))) -1).
Since UN? N2 and due to Lemma 3 we have [NP
therefore (N
S
(11 (1+aamdd)))))) -1 -1) ( (loo MJ 1) Olog M). Hence, the theorem follows.
L
Similar to Lemma 1, we have the following lemma.
V5-1 Lemma 4. |!? < ((1 sim(072) -1). where 0 cos" ( ++++1440) and x 2
Proof. Due to (Devroye et al., 1996. Lemma 5.3), for any fixed 0 E (0, T/2) we need at most ((1 sim(0/2) ) -1) hyper-cones with angle 20 completely cover Rdd, As result, for any fixed
E (0, π. /2), we need at most ((++ (1++))()777))
d -1 hyper-spherical blocks H(i, 0) to completely
17

---

Published as a conference paper at ICLR 2025
cover the annular region A,. Now, we will show that in each hyper-spherical block our algorithm places only one point. Let 91 be the first piercing point placed by ALGO-CENTER in H..0- For a contradiction, let assume that ALGO-CENTER places another piercing point 92 H,,,, where 42 center of some ellipsoid a E zp- Since a contains points and f2, and the distance between them is least r;. Due Claim 3 the maximum distance between any two points in Hi is most rt. As a result, a is already pierced by Q1- This contradicts that our algorithm places two piercing points in H1. Hence, ALGO-CENTER places most one piercing point in the hyper-spherical block 14,00 to pierce an ellipse in Ip, Hence, the lemma follows.
Claim 3. The distance between any two points in Hi, is at most T/.
11
71
n1
171
m71
m
m
20
20
20
P
(a)
(b)
(c)
(d)
Figure 5: (a) Description of the plane P. (b) Illustration of triangles Amy x' and Anf x'_ (c) Illustration of triangles Loox' n and Alx'n n (d) Illustration of triangles oox mn and Axt' Ae'Em, in T-
Proof. Observe Figure 5, where detail of the projection hyper-spherical block is depicted. Note that the maximum distance between any two points in T,, is most max (In, on). First, consider the triangle Alpn (see Figure 5). By the cosine rule of the triangle, we have:
En
pp + +pm² -
2pl pn cOS (20)
M
M
M
M
+
-
cos(28)
11 + x)
21+2)=-2
M
2
1
2
+1-2
cos (20)
(1 + x)
(1+x)
(1+x)
M
(1+ (1 x)² 2(1 x) cos (20)
(1 + x1+
Since cos (1 + 14/7) and x امك cos(20)
(x+2) 2[++] and x² + x = 1. Now
2
substituting these values in the above equation, we get
En o (1+ (1+ (1+ (2+ x)) = r (1 (1+1 1 x² + 2r - 2x) = = (x² + x) = (ri)²
Now, consider the triangle oopn (see Figure 5).
Here we have:
M
2
M
2
M
2
on -2
cos (20)
(1 - cos (20))
a(1 + -2)-2
a(1 + x2
a(1 + x)
M
=2
(1 + x)) (1 cos (20) = 21 + x)² (1 cos (20))
a<l1 + +))--
Now substituting the values of cos(20)
(x+2) = 2(z+1) and x² + x = 1 in the above equation, we get
1- (x 22)
on² -2 + x²²
2(x 1
(2(x + 1) (x +2)
-2r + xx2
2(x +1)
=r?(1 x)x (r:)2.
18

---

Published as a conference paper at ICLR 2025
Note that In on P/- Thus is the maximum distance between any two points in the region Hs.0-
B.3 MISSING PROOFS OF SECTION 4.3
Efficient implementation of the algorithm. For the efficient implementation of the algorithm. given a fat object a E I centered at with width 8, it is crucial to determine the layer Lg to which the fat object belongs. This can be done in (11) time, since logg s. Next, identifying the closest
point from II to the fat object's centre is important, and according to the following lemma, it can be done in ((d) time.
Lemma 5. For any point q in TR.,, there exists a point r in IT2 such that deo (g. 4 Güven the center, of the fat object, the closest point r E IPa can be found in O(d) time.
Proof. Notice that for any point E It each coordinate of is integral multiple of ε,. For
any point q E R. for each E [d]. the jth coordinate of the point q can be uniquely written as ((r,) = 2j Vj. where 2j f and yj E (0, Here, by 3 we mean the set [8z }
Now, we define the best point r of IT's depending on the coordinates of q. For each j E [d], we set the jth coordinate of as follows.
2/. if y, E 00, ) 24 +lg
r(x,))
y E 122 Cg).
As per the construction of the point r. we have lr(z,) q(,,)) for each j E [d]. As a result,
doe (r;q) g) = maxjeld (r(x)) 4(x;)) < 4.
Correctness of the algorithm. Due to Lemma 5, there exists a point r E II' such that (c, r) S lj. Recall that any fat object in T, has width least fj. it contains hypercube with side length least lj. Thus, E T.j must contain at least r. Hence, the above-mentioned online algorithm is a feasible algorithm.
Analysis of the algorithm. Let Z be a set of input fat objects presented to the algorithm. For each j E [2 log + let I, be the collection of all fat objects in belonging to the layer Lj. Let N and OPT be two piercing sets for I returned by our algorithm and an offline optimal, respectively, for the input sequence I. Let NV, be the piereing sets returned by our algorithm for Iz. Let p any piercing point of offline optimal OPT. Let T, C I be the set of input fat objects pierced by the point p. For each j E [2] log M] + 1] U {0). let Ip.j I, nIj. Let N₂ be the set of piercing points placed by our algorithm to pierce all the fat objects in Ip. For each E [2llog MJ + 1] U (0), let No. = =N, N,, be the set of piercing points explicitly placed by our algorithm to hit hypercubes in Ip.j- easy to see that A Up UpEOPT (ujles MI Nps). Therefore, the competitive ratio of our algorithm is upper bounded by maxpeoPT (2llog MJ + 1) x max, (Wpa)).
Let c be the center of an object a E Ip.-- To hit o, our algorithm adds a point r e HI such that d(r, c) < 4 (due to Lemma 5). Since i the center of E Ip.j having width strictly less than uy and a. have d(c, p) Consequently, we have d(r,p) S 2y + 4. Hence, an open hypercube H, of side length 2u, + lj. centered at p. contains all points in Np.j- Notice that u, 2 $6z. As result, H, is open hypercube of side length ( 3)
Now, using triangle incquality, we have d(r,, p) d(r, c) +d(c,p)()
Observation Let a be a hypercube with side lengths between EB and r3, where l, r. and B are positive real numbers such that E Then, the object a contains at least [e] and at most |r +1+17 +1 points from (3
Due to Observation 1, any open hypercube of side length 2 2 1) contains at most 2 g jd points from 1I Thus, we have W.pli < L _d. Recall that [N u U!log m] W.ril Thus, we
have WN < 2 ( log MJ 1).
19

---

Published as a conference paper at ICLR 2025
C PSEUDO-CODES
Algorithm Algorithm ALGO-INTERVAL for Construction of Online E-Net A for arbitrary inter- vals
Initialize net N 0
2:
while new interval arrives do
3: if (a n| < e|X] then
4:
Ignore a.
5: else
6:
if is already hit by N then Ignore σ.
7:
8:
else
9:
Sort the points in a n X' as p1; Pa....... "12:.--:loox'l1
Hit with points indexed by |onx]] and Add these points to N.
| lanx
11:
end if
13: end if
14:
end while
15:
Return /
Algorithm Construction of Online e-Net N for axis aligned rectangles
Fix random sample P X
2: Construct a balanced binary tree T over P
3: For each node v, construct the set of maximal open P, rectangles Ma
4: For each rectangle M E .M define, WM s|Mnx
5: Construct the safety-net Nas for each M M
6: Initialize empty set: SN = (
7: while imput g-heavy rectangle introduced do
8: if a nP = then
9:
if a nSN then
10:
Find the highest node such that l, intersects an
11:
Identify a subrectangle o' C a s. |o'l < 2 Extend o' to form a P-unhit rectangle M M,.
12:
13:
Add points from safety-net Nas to SN.
14:
end if
15:
end if
end while
17:
return the final online net N = SN...
20


Reviews:
[{"review_id": "Y2YRWDBqhb", "reviewer": "Reviewer_bAWb", "summary": "This is a theoretical paper that gives algorithms to construct epsilon nets and piercing sets for geometric objects that appear in an online setting. The size of the nets and piercing sets are tight in terms of the competitive ratio i.e. the largest ratio of the size of the net returned by the algorithm to the optimal size of the net at any point in the online setting.", "questions": "See Weaknesses and address them", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) Epsilon nets are very important in the field of computational geometry and learning theory. It appears that very less work is done regarding construction of epsilon nets/piercing nets when the objects appear in an online manner. Hence the paper will be of interest to the community.\n\n2) I tried to check the proofs in the main part of the paper to the best of my ability and the paper appears to be sound.\n\n3) The techniques/insights described here might be useful to construct epsilon nets for other objects also. I appreciate the use of figures to convey certain ideas.", "weaknesses": "1) The writing and the presentation of the paper is very weak. Parts of the paper are very abstract. Certain words and concepts appear earlier and are explained later and that too in abstract manner. The writing is repetitive also. Here I give few specific examples:\n\ni) In the Notation and Preliminaries section there is hardly any difference in the definition of online epsilon net and online piercing set. \n\nii) Terms like ranges, range space are used in the introduction section without properly defining them.\n\niii) You can give simple examples for what can be $\\mathcal{X}, \\mathcal {R}$ etc. in the introduction itself. The final results can be abstract but at least some examples might help understand the terminology better.\n\niv) It would be better to bring the pseudo code of the algorithms in the main paper\n\nThe writing and presentation need to be improved a lot.  In the current state the paper will not be accessible to a broad audience.\n\n2) It is not clear from the paper what are the technical challenges faced to maintain an epsilon net in the online setting. Please clarify as it will help highlight the novelty as to why the techniques of constructing the epsilon net differ from the offline case. For this you can add a small paragraph has to how epsilon nets can be constructed for similar object in the offline setting and why it is difficult to modify such algorithms for the online setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1uhoR5pHMH", "reviewer": "Reviewer_UMQk", "summary": "The paper tackles the problems of online $\\epsilon$-nets and online piercing sets for geometric concepts, specifically focusing on bounded VC-dimension and various types of geometric shapes such as intervals, axis-aligned boxes, and ellipsoids. The authors introduce several new algorithms that achieve optimal or near-optimal competitive ratios for these problems, marking the first known results in several of these areas.", "questions": "1. Can the authors extend their algorithms to work efficiently in higher dimensions, and if so, what are the expected challenges and potential solutions?\n2. It would be beneficial if the authors could compare the performance of their online algorithms against existing offline methods to highlight the trade-offs and benefits more clearly.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is one of the first to tackle online $\\epsilon$-net and piercing set problems with a formalized approach, filling a noticeable gap in the existing literature.\n2. The work provides clear proofs and establishes bounds on the competitive ratios of the proposed algorithms.", "weaknesses": "1. This paper mainly focuses on lower-dimensional cases (one-dimensional intervals and boxes in up to three dimensions). Many practical problems exist in higher dimensions, and the algorithms’ performance and applicability might not extend well to such cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WHEL7wcEpB", "reviewer": "Reviewer_RbqL", "summary": "The paper studies the online $\\epsilon$-net problem and the online piercing set problem for geometrical objects. \n\nFor the online $\\epsilon$-net problem, the paper considers the range space of intervals in $\\mathbb{R}^1$ and axis-aligned retangles in $\\mathbb{R}^2$ and $\\mathbb{R}^3$. For intervals, the paper gives an algorithm with asymptotically tight competitive ratio $O(\\log(1/\\epsilon))$. For axis-aligned rectangles, the paper gives an algorithm with nearly asymptotically tight competitive ratios ($O(\\log(1/\\epsilon))$ in $\\mathbb{R}^2$ and $O(\\log^3(1/\\epsilon))$ in $\\mathbb{R}^3$). \n\nFor the online piercing set problem, the paper considers the range spae of axis-aligned boxes, ellipsoids, and fat objects in $\\mathbb{R}^d$ for general $d$. For axis-aligned boxes and ellipsoids, the paper gives an algorithm with an asymptotically tight competitive ratio $O(\\log(M))$, where $M$ is the length range of the geometrical objects. For $\\alpha$-fat objects, the paper gives an algorithm slightly improving the existing $ O\\left(\\left(\\frac{2}{\\alpha}+2\\right)^d \\log M\\right)$ competitive ratio to $O\\left(\\left(\\frac{2}{\\alpha}+\\frac{7}{8}\\right)^d \\log M\\right)$ for $\\alpha \\in [1/2,1]$", "questions": "1. The paper begins with an extensive discussion on VC-dimension; however, it does not utilize this concept in any of the subsequent analyses. All results depend solely on the Euclidean dimension, making the discussion of VC-dimension somewhat distracting for the reader. I recommend either removing this discusstion entirely or clearly articulating the relationship between the results and VC-dimension.\n\n2. The connection between the paper's results and existing literature is not sufficiently clarified.\n\n2.1. The authors claim that their results are asymptotically optimal. Could you specify which variable you are considering for the asymptotic limit?\n\n2.2. The authors reference several existing lower bounds, some expressed in the forms $\\log(n)$ and $\\log(m)$. These bounds do not appear directly comparable to the results presented in this paper. Please elaborate on the relationships, similarities, and differences between these bounds and yours.\n\n2.3. In line 132, the authors introduce a bound of the form $\\log(M)$ without defining $M$, immediately following the introduction of the variable $m$. This lack of definition creates confusion, particularly regarding the similarity between uppercase $M$ and lowercase $m$. I suggest defining $M$ and potentially selecting a different variable to avoid this ambiguity.\n\n3. Several terms and concepts lack formal definitions:\n\n3.1. I recommend that the authors formally define $\\epsilon$-nets in Section 2.\n\n3.2. What is the definition of the hitting set problem? The authors frequently mention it and compare it to the piercing set problem without providing a clear definition. Since the paper does not focus on the hitting set problem, I suggest removing this discussion to maintain focus and coherence.\n\n3.3. In line 42, the definition of a range space is missing.\n\n3.4. The dual range space is introduced in line 75, but its definition is not provided until the following page.\n\n3.5. The parameter $\\alpha$ related to an object is not defined until later in the text (line 93).\n\n3.6. In line 130 (and many other places ao, line 130 is just an example), the authors use the variables $P$ and $X$ interchangeably without defining $P$.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper studies fundamental problems (online eps-net and online piercing set). The problem settings considered(range spaces of intervals, rectangles, ellipsoids, and fat-objects) are interesting and natural. The paper makes good contributions on these problems. In some problems, the paper achieves asymptotically optimal competitive ratio. \n\nOverall, I believe the paper makes good contributions to a natural problem. Its contributions are worthy to publish.", "weaknesses": "The main weakness lies in the writing of the paper. The writing lacks rigor and causes distraction. Many concepts are not clearly defined. Some concepts are not clearly utilized. The connection between the existing results and this paper's result is not clearly stated. I have detailed these issues scifically in the Questions section below.\n\nOverall, I believe the paper has the potential to be decent-to-good, provided that its writing is polished.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M1iIY52pFI", "reviewer": "Reviewer_42wh", "summary": "This paper addresses the online ε-net and online piercing set problems for geometric concepts in computational geometry.  Specifically, it proposes  randomized algorithms for axis-aligned boxes in two- and three-dimensional spaces, achieving near-optimal competitive ratios, and  online algorithms for the piercing set problem  for more complex structures like ellipsoids and axis-aligned rectangles, presenting competitive ratios.", "questions": "1. While the theoretical competitive ratios are well-established, there is little discussion on the real-world computational cost. Does the approach become impractical under frequent updates, and if so, what modifications could reduce the computational load?\n2. The paper does not provide a sensitivity analysis on the effect of different random sample sizes P in Section 3.2, which could significantly affect performance. Without such an analysis, it’s unclear whether the algorithm can reliably achieve near-optimal competitive ratios across different datasets and problem scales. How robust is the algorithm for online ε-nets under varying sample sizes?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novelty in Online Setup: The transition from offline to online algorithms for ε-nets and piercing sets addresses a gap in existing research. This online focus adds significant value to applications in dynamic learning environments.\n2. Comprehensive Theoretical Analysis: Each algorithm is rigorously analyzed for its competitive ratio, demonstrating tight bounds for several common geometric configurations.", "weaknesses": "1. The competitive ratios for higher dimensions grow rapidly, limiting the algorithms’ effectiveness in high-dimensional applications (e.g., for dimensions $d \\ge 4$). This can restrict practical use in real-world, high-dimensional datasets.\n2. The results are mainly for regular, axis-aligned geometric objects (boxes, ellipsoids), yet real-world applications often involve irregular or rotated shapes. Without additional adaptability, the proposed algorithms would struggle in cases where piercing sets are needed for non-standard objects.\n3. In the randomized approach for axis-aligned rectangles, a binary search tree is constructed over a subset of points, dividing intervals repeatedly until only ε-heavy regions remain. While theoretically sound, constructing and updating such a binary tree might be impractical in real-time applications due to overhead. A practical complexity analysis or alternative for dynamic binary tree maintenance would make the algorithm more viable.\n4. The paper is heavily theoretical, with limited discussion of empirical validation. Experiments comparing the proposed algorithms' performance to existing methods would strengthen the practical implications.\n5. Overall, I think this is a good paper, but might not be quite suitable for ICLR. Maybe the computational geometry or theory conferences, like SoCG, are more appropriate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)