Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
578
questions with no upvoted or accepted answers
6
votes
0
answers
642
views
Unique domino tiling
Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset $S$ of the $xy$-plane is star-convex if there ...
- 1,070
6
votes
0
answers
273
views
balls in arrangements of hyperplanes
The following theorem is from Aronov, Naiman, Pach and Sharir's
An invariant property of balls in arrangements of hyperplanes. I would like to state them and then ask if any related problem/theorem ...
- 61
6
votes
1
answer
285
views
A conjecture (or theorem?) on unit vectors in a Euclidean space
I have heard (if I am not mistaken) that there exists the following conjecture (or theorem?).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists ...
- 21.1k
5
votes
0
answers
71
views
Is the choosability/list chromatic number of a circular arc graph equal to its chromatic number?
In 2003, Prowse and Woodall proved that for graphs $C_n^k$ which are powers of cycles,
$$\chi_\ell(C_n^k) = \chi(C_n^k).$$
They conjectured that this equality holds for the broader class of graphs ...
- 151
5
votes
0
answers
172
views
Tiling with triangles of same circumradius and inradius
Consider a pair of positive real numbers $r$ and $R$ with $r<R/2$. Then we can form infinitely many triangles all with circumradius $R$ and inradius $r$.
For any such pair, the resulting triangles ...
- 5,493
5
votes
0
answers
150
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,368
5
votes
0
answers
218
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 ...
- 433
5
votes
0
answers
235
views
Arrangement of points, lines, and planes
Is it possible to construct a finite nontrivial arrangement of points, lines, and planes in 3-dimensional Euclidean space with the following properties?
every line is incident with four points and ...
- 2,689
5
votes
0
answers
177
views
The existence of $n$-sided cells in regular $m$-gons
For any integer $n >= 3$, does there exist a regular
$m$-gon with all diagonals drawn containing a cell with $n$ sides?
See A342222 and its cross-references.
Regular polygon on the Wiki.
&...
- 231
5
votes
0
answers
88
views
Which polytopes can be deformed while keeping their edge-lengths?
Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while
keeping its combinatorial type, and
keeping its ...
- 12.6k
5
votes
0
answers
301
views
Trade-off between covering number, ball radius and diameter of $d$-dimensional shapes
Given any $d$-dimensional shape $X$ in the Euclidean space, let $\ell(X)$ be the length of the longest line segment connecting two points of $X$. How can we prove the following statement?
There exists ...
- 1,677
5
votes
0
answers
198
views
Existence of a honeycomb composed by nearly-hyperspherical $d$-dimensional cells having the same shape and size
Let $\mathcal{H}$ the class of all honeycombs composed by $d$-dimensional cells $C$ having all the same shape and size in a $d$-dimensional space $\mathcal{S}$.
Let $s(C)$ and $\ell(C)$ be ...
- 1,677
5
votes
0
answers
105
views
To choose a set of $n$ rectangles which together form largest number of rectangular layouts
Question: Given a number $n$, find that set of $n$ rectangular tiles of any area and perimeter (the tiles in the set could be any type of rectangles; one could choose some of them as identical, some ...
- 5,493
5
votes
0
answers
136
views
On convex regions containing (and contained within) a given triangle
Given an arbitrary triangle T.
How does one find the convex region C_M of largest area containing T such that T is also the largest area triangle that is contained within C_M?
Guess: for any T, ...
- 5,493
5
votes
0
answers
81
views
Minimize number of lattice paths below a given path
Every north-east lattice path (NE-path) $v$ from $(0,0)$ to $(k, a)$ can be identified with a sequence $0 \le \lambda_1 \le \lambda_2 \le . . . \le \lambda_k\le a$, that represent the hight of each ...
- 51
5
votes
0
answers
173
views
Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles
Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...
- 19.1k
5
votes
0
answers
150
views
Random walks in arrangements of lines in the plane
Let $\cal{A}_n$ be a simple arrangement of $n$ lines in $\mathbb{R}^2$.
(Simple: each pair of lines meet in a distinct point, i.e.,
no three lines pass through the same point.)
Start a random walk at ...
- 149k
5
votes
0
answers
275
views
Can we represent partitions by mutually parallel lines in the plane?
Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...
- 1,267
5
votes
0
answers
158
views
Polychromatic number of plane
Let $\chi$ be the least size of a partition of plane into pieces each of which omits unit distance. Let $\chi_p$ be the least size of a partition of plane into pieces each of which omits some distance....
- 51
5
votes
0
answers
362
views
Shapes defined by points
Can shapes determined by some number of points?
From an amazing theorem in plane curves geometry we know that vertices of triangles similar to arbitrary triangle $T$ is dense on every closed jordan ...
- 289
5
votes
0
answers
487
views
Longest simple path through hypercube corners
This is a variation on a previously answered question,
Longest path through hypercube corners.
Here I am seeking the longest simple (non-self-intersecting) path through
the unit hypercube's vertices,
...
- 149k
5
votes
0
answers
203
views
Polynomials representing locally constant functions
Let $K$ be a finite field with $p$ elements.
(a) Let $f\in K\lbrack x\rbrack$ be such that (i) $\deg(f)<p$ and (ii) $f(2x) = f(x)$ for $\geq (1-\epsilon) p$ values of $x$ in $K$. What can we say ...
- 19.4k
5
votes
0
answers
135
views
What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?
Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
- 13.2k
5
votes
0
answers
405
views
Algorithm to express a point from a H-polyhedron as convex combination of extreme points
Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is,
$$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$
Let $\boldsymbol{x} \in P$. We ...
- 607
5
votes
0
answers
295
views
Biggest (or large) rectangle in a polytope
I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...
5
votes
0
answers
207
views
Visibility in a prime orchard
This suggests a variant on Polya's orchard problem.
That problem asks1
for which radius $\epsilon$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the ...
- 149k
5
votes
0
answers
935
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 ...
- 151
5
votes
0
answers
263
views
Coloring $\mathbb{Z}^k$ and a fixed point theorem
This is potentially another approach to this question. I put it as an update there, but perhaps it would be better to post it separately. If we color $\mathbb{Z}^k$ with the $\ell_\infty$ metric in ...
user6976
4
votes
0
answers
111
views
Hyponontiling Wang tiles
Call a finite collection of tiles that can tile the plane if we have to use each tile at least once tiling.
Is there a collection of at least 3 tiles that is not tiling, but such that after removing ...
- 18.4k
4
votes
0
answers
170
views
Can a square be partitioned into mutually non-congruent triangles all of same area and perimeter?
It is known that the plane cannot be tiled by pair-wise non-congruent triangles all having same area and same perimeter (https://arxiv.org/abs/1711.04504).
Question: Can a square be partitioned into ...
- 5,493
4
votes
0
answers
212
views
Economic equilibrium and tropical geometry
There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...
- 113
4
votes
0
answers
303
views
Regular solids and $\mathbb{Z}_5$
The mapping from the regular solids to $\mathbb{Z}_5$ given by the number of faces in the solid mod 5, interestingly, is a bijection. Any geometers or algebraists know if there is a significant ...
4
votes
0
answers
110
views
Advice on results for balls on regular $N$-dimensional grids
I have obtained some results regarding balls on regular $N$-dimensional grids. I would like expert opinion on wether the results are significant or interesting enough for (trying to) publish them in a ...
- 337
4
votes
0
answers
78
views
Which rectangles can be cut into finitely many rectangles all with same perimeter and different areas?
Ref 1: dividing a square into unique rectangles with the same perimeter
https://arxiv.org/ftp/arxiv/papers/1307/1307.3472.pdf
Ref 1 asks if a square can be cut into some finite number of rectangles ...
- 5,493
4
votes
0
answers
207
views
What does it mean "parallel"?
I am thinking on a strict definition of the notion of parallel affine sets in a linear space and came to the following
Definition 1: An affine set $A$ is parallel to an affine set $B$ in a linear ...
- 40.9k
4
votes
0
answers
150
views
Areas of triangles induced by $n$ points on $\mathbb{S}^1$
Suppose we are given $n$ distinct points $x_1, \dots, x_n \in \mathbb{S}^1$ on the unit circle in $\mathbb{R}^2$. Any three points induce a triangle $\Delta(x_i, x_j, x_k)$ and a total of $\sim n^3/6$ ...
4
votes
0
answers
113
views
Find at least one square-boxed subcontinuum
Recall that a plane continuum is a closed, bounded,
connected subset of the plane.
It is non-degenerate if it contains at least two points.
(We may sometimes just say "continuum" even if
we ...
- 1,345
4
votes
0
answers
131
views
Can a polytopal graph be "centrally symmetric" in more than one way?
Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory ...
- 12.6k
4
votes
0
answers
128
views
Can a convex frame hold all circles of radius $1/n$ immobile?
Here is a frame that holds circles of radius $1, \frac{1}{2}, \frac13, ..., \frac17$ immobile.
By "immobile", I mean no circle can move without overlapping other circles or the frame, ...
- 2,663
4
votes
0
answers
151
views
On moments of inertia of planar and 3D convex bodies
The following observation can be readily proved using the perpendicular axes theorem and intermediate value theorem: "Given any planar figure C, through any point on it, there is at least one ...
- 5,493
4
votes
0
answers
174
views
To whom is the classification of atomic, modular finite lattices due?
Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
- 22.9k
4
votes
0
answers
141
views
Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$
We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
- 1,677
4
votes
0
answers
99
views
Unit distance graphs with large minimum degree
Inspired by this (now closed) question, I was wondering the following: What is the smallest possible cardinality of a set $P$ of points in the plane such that
no three points in $P$ are collinear,
...
- 2,531
4
votes
0
answers
153
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 ...
- 628
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 ...
- 2,901
4
votes
0
answers
188
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 ...
- 3,926
4
votes
0
answers
54
views
On ways to measure the difference between two planar convex regions
This earlier post attempted to quantify the difference between a pair of planar convex regions of equal area and perimeter using Hausdorff distance:
On comparing planar convex regions of equal ...
- 5,493
4
votes
0
answers
121
views
Find a good drawing for the edges of any two component of $G-S$ that do not cross
A drawing of a graph $G$ on the plane $P$ is a representation of $G$, where vertices are distinct points in $P$, and edges are Jordan arcs in the plane joining the points corresponding to their end ...
- 1,615
4
votes
0
answers
111
views
Projective planes over algebraically closed fields
Suppose I am given a projective plane $P \cong \mathbb{P}^2(k)$ over a (commutative) field $k$.
With "projective plane," I mean the point-line geometry (and not, for instance, the scheme): $...
- 4,353
4
votes
0
answers
229
views
Illuminating a just-barely irrational polygon
As has been discussed earlier on MO,1,2
recently an impressive advance was proved concerning
internally illuminating a mirrored polygon.
Here is the result:
Let $P$ be a rational polygon.
Then for ...
- 149k