Questions tagged [covering]

The tag has no usage guidance.

28 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
0 answers
934 views

N-balls covering n-balls

This question is a follow-on question from: Covering a unit ball with balls half the radius The questions are these: Given an arbitrary dimension d, and a unit n-ball in d-dimensional Euclidean ...
Rob Bird's user avatar
  • 151
4 votes
0 answers
107 views

Sufficient conditions for the Besicovitch covering theorem to hold on groups of polynomial growth

Let $G$ be a finitely generated group with symmetric generating set $S$. Then $S$ induces a distance $d$ on $G$ by letting $d(a,b) = $ the minimum $n$ such that there are generators $s_1,...,s_n$ with ...
MathidRyan's user avatar
4 votes
0 answers
89 views

Can we replace 2-fold cover by n rectangles with 1-fold cover by n rectangles?

Suppose that $n$ rectangles cover every point of their union exactly twice (except for points on their boundaries). Can we partition this union into at most $n$ rectangles? I think it's pretty ...
domotorp's user avatar
  • 18.3k
4 votes
0 answers
319 views

Besicovitch's covering theorem for ellipsoids and shadows

The usual Besicovitch's covering theorem concerns closed balls in $\mathbb{R}^d$. It relies on a property called "directionally limited metric space": the principal ingredient is to say that there can'...
Alvaro's user avatar
  • 41
3 votes
0 answers
131 views

Enumerating 1-Lipschitz functions on an integer grid

Let $G$ denote an integer grid consisting of $\{0,\dots,m\}\times\{0,\dots,n\}$. An integer-valued function $f:G\to\mathbb{Z}$ is said to be 1-Lipschitz if it satisfies $|f(x) - f(y)| \leq \| x-y \|$...
Tom Solberg's user avatar
  • 3,929
3 votes
0 answers
119 views

Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large. An agent can move in the area at ...
lchen's user avatar
  • 459
3 votes
0 answers
423 views

Tiling a rectangle with weighted cells (min-max problem)

I have been struggling with a research problem. The problem can be formalized as follows: Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ ...
SaSa's user avatar
  • 31
3 votes
0 answers
86 views

Between Cover and Partition

In a cover problem, there is a complex shape (e.g. a polygon), and we have to find a set of simpler shapes (e.g. squares or rectangles), such that their union is exactly equal to the complex shape. A ...
Erel Segal-Halevi's user avatar
3 votes
0 answers
326 views

Examples of Sheafification via Hypercovers

For a presheaf $F$ on a category equipped with a pretopology, one has the sheafification $F^{\sharp}$ of $F$. I know well the plus-construction of sheafification, which is presented in Artin's paper "...
Hiro's user avatar
  • 945
3 votes
0 answers
460 views

Galois group decomposition of non-cyclic covers

If $\pi: C \rightarrow \mathbb{P}^{1}$ is a cyclic cover of $\mathbb{P}^{1}$ with Galois group $\mathbb{Z}/m \mathbb{Z}$ and thus with the (affine) formula $y^{m}= (x_{1}-a_{1})^{t_{1}}....(x_{n}-a_{...
Jack's user avatar
  • 637
2 votes
0 answers
81 views

Fundamental group of a quotient by a group action

Suppose I have a quotient $X \to S$ by a finite abelian group $G$ action (I have several cases, but in all of them the group $G$ and the action could be written explicitly), where $X,S$ are surfaces (...
Manenky's user avatar
  • 21
2 votes
0 answers
86 views

How many ways to cover a N×N chessboard with white and black boxes by some restrictions?

Suppose we have a N×N chessboard and the boxes ■, □. We should cover the chessboard with those boxes but there can not have the 2×2 square $\scriptstyle{\begin{array}{cc}\square&\square\\ \...
Yuhuan Lei's user avatar
2 votes
0 answers
259 views

Covering number for the unit ball in a reproducing kernel Hilbert space

I am looking for a reference for an upper bound on the covering number for the unit ball $\{ f \in \mathcal{H}: ||f||_{\mathcal{H}} || \leq 1\} $, where $\mathcal{H}$ is a reproducing kernel Hilbert ...
JohnK's user avatar
  • 121
2 votes
0 answers
145 views

Cardinality of compact doubling metric spaces with fast growing covering numbers

In this question it was established that if the growth of the number of branches of an at-most $k$-branching tree is $\Omega(k^n)$ (in the Knuth sense), then the tree has continuum many branches. ...
James Hanson's user avatar
  • 10.3k
2 votes
0 answers
450 views

Finding good high-dimensional sphere coverings in Euclidean space

Suppose we want to cover the unit sphere $\mathcal{S}^{d-1} := \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ with spherical caps $\mathcal{C}_{\mathbf{y}} := \{\mathbf{x} \in \mathcal{S}^{d-1}...
TMM's user avatar
  • 713
1 vote
0 answers
140 views

Relation between projective representation and the representation of the universal cover of a Lie Group

I am reading this paper, in what says exactly: "Weare dealing with a ray representation os the conformal group AND THEREFORE with a representation of the universal covering group of the conformal ...
Gabriel Palau's user avatar
1 vote
0 answers
57 views

Admissibility of representations induced from Hecke algebra for covering groups

Assume $G$ is a semisimple algebraic group and $B$ is an Iwahori subgroup. Let $(r,E)$ be a representation of $H(G,B)$ which is an Iwahori-Hecke algebra, then Borel proved that $C_{c}(G/B)\otimes_{H}E$...
Fuutorider's user avatar
1 vote
0 answers
39 views

Separation of balls in the torus

Let $X_1, \dots, X_N$ be $N$ balls of radius $R<<1$ in $[0,1]^d$ such that $N R^d \leqslant R^{\alpha}$ for some $\alpha > 0$ and $d(x_i,x_j)\geqslant 2R$ for any $i\not=j$. The assumption ...
JBB's user avatar
  • 11
1 vote
0 answers
49 views

Minimizing the set of multiply covered elements in a linear hypergraph

We say that a hypergraph $H=(V,E)$ is a linear hypergraph if it has the following properties: if $e_1\neq e_2\in E$ then $|e_1\cap e_2|\leq 1$, and $\bigcup E = V$. We say that $C\subseteq E$ is a ...
Dominic van der Zypen's user avatar
1 vote
0 answers
64 views

When does a metric space admit finite covers by Voronoi diagrams of Delone sets?

Some preliminary definitions: For a given metric space $(X,d)$ and set $A\subset X$, the Voronoi diagram of $A$ (which I'll write $V(A)$) is the collection of sets of the form $$C_a=\{x\in X|\forall b\...
James Hanson's user avatar
  • 10.3k
1 vote
0 answers
68 views

Covering number of the range of a function

I have come across the need to know a bound on a certain curious quantity: the covering number of the range of a continuous function $f: D \rightarrow \mathbb{R}^n$, where $D \subseteq \mathbb{R}^m$. ...
Ankur's user avatar
  • 183
1 vote
0 answers
65 views

Approximating Unit covering of d-dimensional points

Given a $d$-dimensional disk of radius $2$ in $\mathbb{R}^d$, how many disks of radius $1$ suffice to cover it. Of course, it's fine if the smaller disks overlap. What matters is to specify a finite ...
user3609721's user avatar
0 votes
0 answers
23 views

Approximation of connected set by triangluation / covering by simplices

Good afternoon. I have two distinct questions: If I have connected compact in $\mathbb{R}^n$, how much $(n+1)$-simplices are needed to fill its interior such that diameter of maximal uncovered part ...
Dmitry Vilensky's user avatar
0 votes
0 answers
81 views

Efficiency of covers

Let $X\neq \emptyset$ be a set. We say $C \subseteq {\cal P}(X)$ is a cover of $X$ if $\bigcup C = X$. For covers $C, D$ of $X$ we say that $C$ is more efficient than $D$ if $|C\setminus D| < |D \...
Dominic van der Zypen's user avatar
0 votes
0 answers
103 views

Optimal covering trails in 3 and 4 dimensions

A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of ...
Marco Ripà's user avatar
  • 1,119
0 votes
0 answers
113 views

Odd covering system without modulus 3 (mod3)

The existence of odd covering system with distinct moduli is a famous open question proposed by Erdős and Selfridge. I wonder whether a restricted condition for the problem that odd covering system ...
user1851281's user avatar
0 votes
0 answers
73 views

On finding optimal convex planar shapes to cover a given convex planar shape

Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
Nandakumar R's user avatar
  • 5,453
0 votes
0 answers
539 views

Ramified covering interpretation of an elliptic curve

Let $E:y^2=x(x-1)(x-\lambda)$ be the Legendre form of an elliptic curve $E$ defined over $\mathbb{C}$. The ramified covering $E\to \mathbb{P}_{1}$ defined so that $(x,y)\mapsto x$ has two branches and ...
Hair80's user avatar
  • 655