Questions tagged [discrete-geometry]

Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

Filter by
Sorted by
Tagged with
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 ...
Cemo's user avatar
  • 11
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$...
Penelope Benenati's user avatar
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 ...
trotzt's user avatar
  • 359
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 ...
Joseph O'Rourke's user avatar
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$ ...
hookah's user avatar
  • 1,096
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 ...
Student's user avatar
  • 555
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 ...
Agelos's user avatar
  • 1,844
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 ...
Carlos_Petterson's user avatar
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 ...
Janaka Rodrigo's user avatar
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$ (...
Tassle's user avatar
  • 131
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 ...
Paolo Leonetti's user avatar
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 ...
paul's user avatar
  • 153
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$ ...
mc.math's user avatar
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 ...
Stanley Yao Xiao's user avatar
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 ...
Nandakumar R's user avatar
  • 5,401
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 ...
Arun 's user avatar
  • 725
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 ...
Dr.X's user avatar
  • 81
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 ...
Nandakumar R's user avatar
  • 5,401
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 ...
Roselyn van Lauwe's user avatar
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 ...
Nandakumar R's user avatar
  • 5,401
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 ...
James Propp's user avatar
  • 19.4k
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 ...
Nandakumar R's user avatar
  • 5,401
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 ...
user8469759's user avatar
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$...
Peter K's user avatar
  • 153
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 ...
Nandakumar R's user avatar
  • 5,401
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/...
Mihaela's user avatar
  • 31
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 ...
Nandakumar R's user avatar
  • 5,401
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? ...
M. Rumpy's user avatar
  • 263
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 ...
Vanessa's user avatar
  • 1,368
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 ...
Nandakumar R's user avatar
  • 5,401
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). ...
Nandakumar R's user avatar
  • 5,401
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 ...
Carlos_Petterson's user avatar
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-...
James Propp's user avatar
  • 19.4k
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 ...
Morteza's user avatar
  • 628
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 ...
Nandakumar R's user avatar
  • 5,401
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 ...
Andi Bauer's user avatar
  • 2,901
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 ...
Paata Ivanishvili's user avatar
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....
Nandakumar R's user avatar
  • 5,401
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 ...
Nandakumar R's user avatar
  • 5,401
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 ...
Andi Bauer's user avatar
  • 2,901
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 ...
dohmatob's user avatar
  • 6,706
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-...
dohmatob's user avatar
  • 6,706
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 ...
Shahab's user avatar
  • 433
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 ...
Dustin G. Mixon's user avatar
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 ...
Alan Li's user avatar
  • 71
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 ...
bleh's user avatar
  • 153
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....
Nandakumar R's user avatar
  • 5,401
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 $\...
RyanChan's user avatar
  • 550
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},...
Shiquan Ren's user avatar
  • 1,970
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\}, $$ ...
RyanChan's user avatar
  • 550

1
5 6
7
8 9
37