Questions tagged [discrete-geometry]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
23 views

Endpoints of intrinsic diameter of a convex polyhedron

Let $P$ be a convex polyhedron in $\mathbb{R}^3$, and $d(P)$ its intrinsic diameter, i.e., the longest shortest surface path between two points. Say that $P$ is of class $D_0$ if neither endpoint of $...
user avatar
3 votes
0 answers
57 views

Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$

This should be a fairly standard question but I can't really seem to find a reference. Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
user avatar
11 votes
1 answer
264 views

Complexity of counting regions in hyperplane arrangements

Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$. ...
user avatar
  • 15.6k
5 votes
1 answer
91 views

Partitioning convex polygons into triangles of equal area and perimeter

This post is based on https://math.stackexchange.com/questions/2822589/dissect-square-into-triangles-of-same-perimeter and On a possible variant of Monsky's theorem Question 1: Is this statement ...
user avatar
  • 3,601
1 vote
0 answers
28 views

What are some other methods for partitioning an n-dimensional space based on a set of points in that space?

So this is a very general question, but I'm curious if there are any other methods for partitioning an n-dimensional space based on the location of a set of points, either randomly chosen or specified,...
user avatar
  • 11
-1 votes
0 answers
76 views
+50

Understanding a constant $c>0$ in a problem on mutually avoiding sets of points and lines

I came across the following problem that seems very interesting: if we have four mutually avoiding sets of total of $n$ points (that are in general position), say $\{A_1,A_2,A_3,A_4\}$ (i.e. sets in ...
user avatar
1 vote
0 answers
44 views

Diameter of a Cartesian product of two graphs [migrated]

If I am looking at a Cartesian product of two graphs $G_1$ and $G_2$ (defined here https://en.wikipedia.org/wiki/Cartesian_product_of_graphs). I am trying to bound the diameter of the graph $G_1 \...
user avatar
14 votes
7 answers
2k views

Finite set of non-collinear points on plane with every point having ≥ 3 equidistant neighbors? [closed]

Does there exist a finite set of points on the Euclidean plane, such that: No 3 points are collinear, and Every one of the points has (at least) three other points in the set at the same distance ...
user avatar
  • 159
0 votes
0 answers
33 views

When can a compact metric space be covered by finitely many nearly-disjoint closed and convex sets?

This question is a follow-up of the following negative question. Let $(X,d)$ be a (non-empty) compact metric space. More generally than in the first post, I'll call a set of non-empty subsets $C_1,\...
user avatar
  • 5,124
2 votes
1 answer
49 views

Determining if a polygon is convex using relations on orientation of each ordered triple of points

I am reading a paper by Szekeres and Peters on computing the 17-point case of the Erdős–Szekeres conjecture. The conjecture states that the minimum number of points in the plane (in general position, ...
user avatar
7 votes
2 answers
192 views

Are polyhedra with equilateral triangular faces rigid?

Convex polyhedra are rigid by Cauchy’s theorem. Steffen’s polyhedron is an example of a non-convex polyhedron that is flexible (i.e., non-rigid). However, it appears to have edges of different lengths....
user avatar
  • 172
3 votes
0 answers
123 views

minimal set of words of length n

Given an alphabet $S={a_1,\cdots,a_m}$, we consider the words of length $n$, $S^n$. We call two words $b_1b_2\cdots b_n$ and $c_1c_2\cdots c_n$ are connected if $b_i=c_i$ for some $i$. We consider $P\...
user avatar
  • 1,333
26 votes
1 answer
2k views

Polyomino that can tile itself

Find all polyomino $P$ such that we can tile $nP$ with $n^2$ copies of $P$ for all $n\in \mathbb{N}$. ($nP$ is a polynomino similar to $P$ with scale factor $n$) I conjecture that there are only $4$ ...
user avatar
2 votes
1 answer
134 views

Pairwise intersecting circles in the plane

If I am looking at a collection $\mathcal{C}$ of circles $\{C_1,...,C_n\}$ all of which have some radii $\{r_1,...,r_n\}$ where $r_i\in\mathbb{R}^{+}$ for each $i \in[n]$. In $\mathcal{C}$, all the ...
user avatar
4 votes
1 answer
107 views

On polyhedrons with specified numbers of congruent faces

Basic question: Given 3 integers n, n1 and n2 such that n1+n2 = n, to form an n-face polyhedron such that n1 of its faces are mutually congruent and the remaining n2 faces are different but congruent ...
user avatar
  • 3,601
1 vote
1 answer
49 views

Representation of $x$-non-monotone curves with one intersection each by $x$-monotone curves

Take the $y$-axis and a set of $n$ curves starting from $y$-axis, labelled as $\mathcal{C}:=\{C_1,C_2,...,C_n\}$. These curves fulfill the following conditions: The curves all have a starting point ...
user avatar
2 votes
0 answers
52 views

Tiling with triangles with same Steiner ellipses

We continue from Tiling with triangles of same circumradius and inradius . Definitions: Given any triangle, its Steiner circumellipse is the unique circumellipse (ellipse that touches the triangle at ...
user avatar
  • 3,601
3 votes
1 answer
72 views

Convex polygon shadows: Shortest equivalent segments

Let $P$ be a convex polygon. Q1. What is the shortest collection of line segments $S$ inside $P$ with the property that both $P$ and $S$ have the same sequence of orthogonal shadows as $P$ and $S$ ...
user avatar
41 votes
1 answer
2k views

Does any set of dominoes tile some common figure?

Let $D_1,\dots,D_n \subset \mathbb{Z}^2$ be two-point sets, i.e. 'dominoes' (unlike common dominoes, these are not necessarily connected, but I couldn't come up with a better name). Does there always ...
user avatar
16 votes
1 answer
814 views

Kakeya crossed-needles problem

The Kakeya needle problem asks for the minimum area planar region in which one can completely turn around a line segment through a series of translations and rotations. There is no minimum: There are &...
user avatar
2 votes
0 answers
270 views

Combinatorics of iterated composition of noncrossing partition polynomials

A combinatorial problem arises in relating connected and disconnected Green functions associated to a "zero-dimensional" quantum field theory presented by Brezin, Itzykson, Parisi, and Zuber ...
user avatar
  • 8,308
23 votes
1 answer
557 views

Given a group action on a simplex, can I always find a fundamental region that is a simplex?

Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...
user avatar
  • 10k
1 vote
1 answer
78 views

Triangles that can be cut into mutually congruent and non-convex polygons

It is easy to note that an equilateral triangle can be cut into 3 mutually congruent and non-convex polygons (replace the 3 lines meeting at centroid and separating out the 3 congruent quadrilaterals ...
user avatar
  • 3,601
2 votes
1 answer
248 views

Maximal distance of set to integers

Let $x_1,...,x_N$ be $N$ mutually distinct real numbers. I wonder: How does the expression $$ f_x(N)=\sup_{\lambda \in \mathbb R}\min_{i \neq j} \min_{n \in \mathbb Z}\left\vert \lambda (x_i-x_j)-n\...
user avatar
  • 347
3 votes
0 answers
116 views

Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?

Given the formal Taylor series, or e.g.f., $f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$, the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via $ \sum_{n \geq 1} ...
user avatar
  • 8,308
1 vote
0 answers
36 views

Tiling with a one-parameter family of non-congruent triangles

This post continues Tiling with triangles of same circumradius and inradius. The following are known about infinite sets of triangles that can be parametrized with one variable: from an infinite set ...
user avatar
  • 3,601
4 votes
1 answer
92 views

Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?

Suppose that $P\subset\Bbb R^n, n\ge 3$ is a (full-dimensional) convex polytope with a bipartite edge-graph $G=(V_1\cup V_2,E)$ (for example, a zonotope). Suppose further that there are concentric ...
user avatar
  • 10k
5 votes
0 answers
150 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 ...
user avatar
  • 3,601
3 votes
0 answers
45 views

Simplex cover of an n-cube with non-congruent simplexes

I am curious about simplex coverings of the unit n-dimensional hypercube (or n-cube) with the following properties: The simplexes do not need to be regular The simplexes can be non-congruent (i.e. of ...
user avatar
4 votes
1 answer
192 views

Do combinatorially equivalent polytopes have the same triangulations?

A triangulation of a convex polytope $P\subset\Bbb R^n$ is a partition of $P$ into $n$-simplices $\{\Delta_1,...,\Delta_m\}$ each of which has all its vertices among the vertices of $P$. A polytope ...
user avatar
  • 10k
1 vote
2 answers
85 views

Name for the weight function defined as the integer sum of coordinate entries from ${\mathbf F}_p$

In ${\mathbb F}_p^n$, $p$ prime one may define a weight function on vectors in various ways such as Hamming, or Lee weight. (These two weights correspond nicely to the respective distances from $\bar ...
user avatar
  • 11
1 vote
0 answers
48 views

Convex polyhedron in lattice points

Given $P$ a convex polyhedron with vertices in lattice points with $n$ faces. a) what is the minimum volume of $P$. b) what is the minimum area surface of $P$. Paper: The minimum area of convex ...
user avatar
  • 421
8 votes
0 answers
96 views

Is every simplicial $d$-sphere linearly embeddable in $\Bbb R^{d+1}$?

A simplicial $d$-sphere is a simplicial complex homeomorphic to the $d$-sphere. It is known that not every such complex can be embedded into $\Bbb R^{d+1}$ as the boundary complex of a convex ...
user avatar
  • 10k
0 votes
0 answers
18 views

History and bounds on hinged-ruler-packing problem?

A hinged-ruler of $n$ segments is a sequence $(a_1,a_2,\cdots,a_n)$ of reals from the interval $[0,1]$. The ruler takes the appearance of $n$ line segments joined at their endpoints with hinges, where ...
user avatar
  • 141
5 votes
1 answer
239 views

Contracting a set to a ball

$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$ Question 1: Let $S$ be a nonempty measurable subset of $\R^n$. Let $B$ be a closed ball in $\R^n$ such that $m(B)=m(S)$, where $m$ is the Lebesgue ...
user avatar
8 votes
2 answers
263 views

Symmetries of contractable subsets of $\Bbb R^n$

Let $K\subset\Bbb R^n$ be a non-empty compact subset of $\Bbb R^n$. A symmetry of $K$ is an isometry of $\Bbb R^n$ that fixes $K$ set-wise. Since $K$ is compact, there is always a point $x\in\Bbb R^n$ ...
user avatar
  • 10k
5 votes
0 answers
54 views

Roundest polyhedra: how well can we bound the edge count of their faces?

By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...
user avatar
2 votes
1 answer
132 views

On rigid packings of the plane with a constraint

This post continues Thinnest rigid packings of the plane A packing of the plane with copies of any shape is called rigid (or "stable") if every unit is fixed by its neighbors, i.e., no unit ...
user avatar
  • 3,601
1 vote
0 answers
83 views

cone structure of complement of hyperplanes

I want to know if in $\mathbb{R}^{m+3}$ we consider the following hyperplanes: \begin{cases} (1-g)y-\sum_{i\in I}x_i=0, & \text{if $I\subset\{1,\cdots,m+2\}$},|I|=g\\ gy-\sum_{i\in I}x_i+\...
user avatar
  • 493
33 votes
1 answer
2k views

Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?

I'm trying to figure out the question in the title for a project that I'm working on. My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them ...
user avatar
2 votes
1 answer
66 views

Open covering with bounded diameters [closed]

Here is an interesting puzzle I came across. I have no idea which tools could be applied to solve it, so the tags may be misleading. For any $A \subseteq \mathbb{R^n}$ , its diameter is defined by $$\...
user avatar
9 votes
3 answers
319 views

Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?

A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are ...
user avatar
1 vote
0 answers
56 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 ...
user avatar
  • 11
8 votes
0 answers
277 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$...
user avatar
23 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 ...
user avatar
  • 349
7 votes
0 answers
155 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 ...
user avatar
4 votes
3 answers
203 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$ ...
user avatar
  • 1,076
0 votes
1 answer
44 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 ...
user avatar
  • 505
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 ...
user avatar
  • 1,294
1 vote
0 answers
40 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 ...
user avatar

1
2 3 4 5
32