Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
1,815
questions
1
vote
0
answers
71
views
Is there any previous study on the relationship between convexity and the order of points in the general position?
Let's assume $V =(v_1,v_2,v_3,… ,v_n)$ is a set points in a general-position. For each point $v_i$, let's list the points in the order we encounter as we rotate around a certain direction (say ...
10
votes
0
answers
419
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
24
votes
3
answers
3k
views
Polyomino that can cover an arbitrarily large square but not the entire plane
https://userpages.monmouth.com/~colonel/nrectcover/index.html
For a polyomino with no holes that cannot tile the plane, we may ask what are the maximal rectangles and infinite strips that it can ...
7
votes
0
answers
210
views
Tiling space with supertile of hypercube unfoldings
Two students in my class
asked and answered what might be a novel question.
It is well known that the cube has exactly $11$ edge-unfoldings
(or "nets"), as shown below:
(Image from ...
4
votes
3
answers
246
views
Existence of (near) equidistant codewords
My question is originally related to coding theory, but fairly easy to state in pure combinatorial way.
Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...
4
votes
2
answers
268
views
Bounds on the number of samples needed to learn a real valued function class
Let us see Theorem 6.8 in this book, https://www.cs.huji.ac.il/w~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf
It gives us a lowerbound (and also an ...
14
votes
4
answers
1k
views
A notion of 2-dimensional tree
Summary: This post has got rather long after the discussion. The main still open Questions are 5 & 6 below. There is work in progress, and I'll post an update at some point.
A tree is a connected ...
1
vote
0
answers
43
views
When can infinite graphs be partitioned into trees of a given minimum size
Let $G=(V,E)$ be a graph with $0<\#V\leq \#\mathbb{N}$ and fix $n\leq \#V$. When can $G$ be partitioned into $(V_1,E_1),\dots,(V_m,E_m)$ where $V= \cup_i \, V_i$, $\#V_i\geq n$ and $E_i$ contains ...
1
vote
0
answers
103
views
Different ways of partitioning a convex n -gon [closed]
What is the relationship between Catalan numbers and number of different ways of partitioning the set of vertices of a convex n-gon into nonintersecting polygons?
Catalan numbers sequence describes ...
3
votes
0
answers
207
views
What is the VC-dimension of regular convex k-gons in the plane?
Recall the relevant definitions:
Let $H$ be a family of sets in $\mathbb{R}^d$. The intersection of $H$ with a point set $C$ is defined as $H\cap C = \{h\cap C\mid h\in H\}$. The VC-dimension of $H$ (...
8
votes
1
answer
237
views
A vertical line with many intersections with $n$ non-parallel lines
Pick $n\ge 3$ non-vertical lines $\mathscr{L}:=\{\ell_1,\ldots,\ell_n\}$ in the plane which are pairwise non-parallel, and they are not all concurrent in a single point.
Question. Does there exist a ...
2
votes
2
answers
151
views
Angle between a point in a convex polytope and the nearest point of a face
Let $P \subset \mathbb{R}^d$ be a convex polytope, and let $F$ be a face of $P$ (of co-dimension 1, let's say). Now let $x \in P \setminus F$ and let $y \in F$ be the nearest point of $F$ to $x$. Then ...
0
votes
2
answers
137
views
References for geometric properties of optimal Euclidean traveling salesman tour
Consider a finite set of points $V \subseteq \mathbb{R}^2 $ as a TSP-instance under the standard $\| \cdot \|_2$ norm. (TSP stands for traveling salesman tour.) We know that every optimal TSP tour $T$ ...
0
votes
1
answer
143
views
Matching bins up to shuffling II
Suppose a school purchases a set $\mathcal{S}$ of balls, say
$$\displaystyle \mathcal{S} = \{b_1, b_2, \cdots, b_n\}$$
with $n$ very large. The balls $b_j$ are pairwise distinct and have distinct ...
2
votes
1
answer
65
views
Optimal unions of planar convex regions
This post continues Optimal intersections between planar convex regions.
Question: Given two planar convex polygonal regions $C_1$ and $C_2$, how does one algorithmically find how to place and orient ...
2
votes
1
answer
129
views
Automorphism group of a normal tiling of the plane
A normal tiling of the plane is a tessellation for which every tile is topologically equivalent to a disk, the intersection of any two tiles is a connected set or the empty set, and all tiles are ...
4
votes
2
answers
369
views
Family of shapes that can be tiled into one another
Okay, I'm trying to ask a question which hasn't been asked before, it may be futile, but let's see.
So let's take a square, this will be our shape A. We can tile a 2x1 rectangle by using shapes ...
1
vote
0
answers
48
views
Which pentagon gives least packing density?
We extend Which convex pentagon gives least packing density? by going from convex pentagons to general ones.
Question: Which pentagon gives the least packing density on the Euclidean plane?
Note: All ...
5
votes
1
answer
162
views
Looking for clarification of C-H Sah's definition of abstract scissors congruence
In C-H Sah's book Hilbert's third problem: scissors congruence, the author defines the data for abstract scissors congruence in order to prove Zylev's theorem by combinatorial means in great ...
1
vote
0
answers
49
views
Comparing convex planar regions of equal perimeter and area - 2
We try to extend On comparing planar convex regions of equal perimeter and area .
Given two planar convex regions C1 and C2 both with unit perimeter, we define the difference between C1 and C2 as the ...
27
votes
8
answers
1k
views
Area-differences for lattice triangles in a checkerboard
For positive integers $m$ and $n$, what is the integral of the function $(-1)^{\lfloor x \rfloor + \lfloor y \rfloor}$ on the triangle with vertices $(0,0)$, $(m,0)$, and $(0,n)$?
Pictorially, we are ...
2
votes
1
answer
140
views
On sets of rectangles that can all together form at least one big rectangle
Let us say a set of $n$ rectangles is rectifiable if all $n$ rectangles together form a big rectangle without gaps or overlaps.
Question: How hard computationally is the question of deciding whether a ...
2
votes
0
answers
147
views
Reduced Voronoi diagram
I am currently reading Differentiable Surface Triangulation presented at Siggraph Asia 2021.
I think most of the paper is clear to me, though I keep re-reading through to see if I miss details.
The ...
5
votes
2
answers
407
views
Counting intersections of hyperplanes
This is a dublicate from stackexchange:
Consider two families of hyperplanes $F_1$ and $F_2$ in $\mathbb{R}^d$ both containing $n$ hyperplanes. We have that for all $f \in F_1$ and $g \in F_2$ that $f$...
3
votes
1
answer
298
views
On smallest circles and ellipses containing at least n integer lattice points
Continuing from On circles and ellipses drawn on an infinite planar square lattice, let us record two broad questions: In what follows, "contains" means "either contains within or ...
2
votes
0
answers
86
views
Is there an exact solution for the number of points within a circle of radius r for an honeycomb lattice?
I want to ask if exists an exact solution for the number of points within a circle of radius r for an honeycomb lattice.
I know that it is exist for an square lattice https://mathworld.wolfram.com/...
3
votes
1
answer
175
views
On the thinnest cover of the plane by a given planar convex region
Is the following claim valid?
Claim: Given any planar convex region C, the thinnest cover of the plane with copies of C cannot have any region where more than 2 copies overlap. In general, the ...
8
votes
1
answer
307
views
Inscribed $n$-polytope with $2^n$ vertices of maximal volume
The question is in the title:
Question: Which inscribed $n$-dimensional polytope (inscribed in the unit sphere) with $2^n$ vertices has the largest possible volume?
Is it the $n$-dimensional cube? ...
5
votes
0
answers
149
views
Maximal number of vertices of the intersection of a flat and a hypercube
Consider the intersection of an $n$-dimensional hybercube and an $m$-dimensional flat (affine subspace) which contains the diagonal of the hypercube. This is a convex polytope. What is the maximal ...
1
vote
0
answers
52
views
To partition planar convex regions into n mutually non-congruent convex pieces of equal area and perimeter
This post continues Cutting a spherical surface into mutually non-congruent pieces of equal area.
Question: Given a planar convex region C and an integer n, how does one decide if C can be divided ...
7
votes
2
answers
559
views
Cutting a spherical surface into mutually non-congruent pieces of equal area
Question: For what values of integer $n$ can the surface of a sphere be partitioned into $n$ convex and mutually non-congruent pieces of same area? (convexity could be viewed as geodesic convexity). ...
6
votes
1
answer
277
views
Covering number estimates on closed Riemannian manifolds
Let $(M^n,g)$ be an $n$-dimensional compact and connected Riemannian manifold with sectional curvature bounded above and below by $c,C$. Is it possible/known how to express the external covering ...
6
votes
0
answers
279
views
A natural fragmentation process
Starting from the length-1 list whose only entry is 1, iterate the process of replacing the last (and largest) entry in the list of length $n$ (call that entry $m$) by the two numbers $mU_n$ and $m(1-...
4
votes
0
answers
151
views
Closest integer point to a sphere with radius R
I have a sphere in $\mathbb{R}^d$ with radius $R$ whose center is not necessarily the origin. I am interested in the closest integer lattice point to it. Indeed, it depends on the center location, but ...
1
vote
0
answers
75
views
Convex planar regions with optimal average 'centralness' and 'depth'
For a planar convex region $C$ and an interior point $P$ we define:
the centralness ratio at $P$ is
$$\min\left(\frac{\text{shorter portion of }\chi}{\text{longer portion of }\chi}:\chi\text{ is a ...
4
votes
0
answers
136
views
Combinatorial fiber bundles
Triangulations (as simplicial complexes) and bi-stellar flips are a combinatorial analogue of (piece-wise linear) topological manifolds. I'm looking for a similar combinatorial analogue for fiber ...
4
votes
0
answers
185
views
Min max of a quadratic form of plus-minus ones
Does the following limit exist?
$$
\lim_{n \to \infty}\, n^{-3/2} \min_{a_{ij}=\pm 1}\max_{x_{j}=\pm 1}\left|\sum_{1\leq i <j \leq n} a_{ij}x_{i}x_{j} \right|
$$
There is no any significant ...
1
vote
2
answers
126
views
On convex planar regions that can be cut into only a specified number of mutually congruent and connected pieces
References:
https://math.stackexchange.com/questions/1838617/dividing-an-equilateral-triangle-into-n-equal-possibly-non-connected-parts
On congruent partitions of planar regions
https://research....
3
votes
0
answers
140
views
Optimal intersections between planar convex regions
Here is an earlier discussion that could be related:
On comparing planar convex regions of equal perimeter and area
We are broadly interested in placing two given planar convex regions so that the ...
2
votes
0
answers
67
views
Triangulations with discrete metrics and conformal equivalence
A discrete metric for a triangulation of a 2-dimensional manifold is a map associating $\mathbb{R}_+$-valued lengths to all edges, such that the triangle inequality holds on every triangle. In many ...
2
votes
1
answer
111
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
2
votes
1
answer
119
views
Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$
Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
5
votes
0
answers
217
views
Lower bounds for the number of bases of a paving matroid
Let $M$ be a paving matroid with $m$ elements and rank $n$. Is there any lower bound for the number of bases of $M$? There is an upper bound for the number of hyperplanes (see here, page 97) but since ...
1
vote
0
answers
55
views
Are sharper lower bounds known for these potentials on the sphere?
Fix a positive integer $\ell$. For $x_1,\dotsc,x_n\in S^{d-1}$, Venkov proved that
$$
\sum_{i=1}^n\sum_{j=1}^n(x_i\cdot x_j)^{2\ell}\geq\frac{(2\ell-1)!!(d-2)!!}{(d+2\ell-2)!!}\cdot n^2,
$$
with ...
7
votes
1
answer
275
views
Open covering of $S^n$ by sets not containing antipodal points
Given an $n$-dimensional sphere $S^n$ and an open cover such that none of the open sets contain antipodal points, does there exist a point on $S^n$ that belongs to at least $n+1$ open sets from the ...
1
vote
2
answers
174
views
Partitioning unit square with equal frequency rectangles
If I had to partition the unit square $[0,1]\times[0,1]$ into $k^2$ rectangles such that the sum of their diagonals is minimum possible, I would simply choose the $k \times k$ grid of squares. Now ...
0
votes
0
answers
72
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....
1
vote
0
answers
153
views
Is there a polynomial expression for the volume of the following set?
Denote the unit $\ell_2$ ball in $\mathbb{R}^n$ as $\mathcal{B}_n$. It is widely kown that for a convex body $\mathcal{K}\subseteq \mathbb{R}^n$, the $n$-dimensional volume of the parallel body $\...
0
votes
0
answers
68
views
packing numbers of the unit balls in Euclidean spaces and the dimensions
Let $k$, $m$ and $n$ be positive integers. Let $r$ be a positive real number.
The $n$-th ordered $r$-disk configuration space on the Euclidean space $\mathbb{R}^{mk}$ is
$$
F_r(\mathbb{R}^{mk},...
1
vote
1
answer
88
views
How to compute external angles of a hypersimplex?
Recently, I concern with the volume of the outer parallel body of a hypersimplex that is defined as follows
$$
\mathcal{H}_s(n,k)=\left\{ (x_1,\cdots,x_n):\sum_{i=1}^n x_i=k,x_i\in[0,1] \right\},
$$
...