# Questions tagged [discrete-geometry]

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

1,559 questions
Filter by
Sorted by
Tagged with
23 views

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 ...
33 views

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$ ...
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 ...
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 ...
1 vote
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 ...
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 ...
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$ ...
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 ...
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 &...
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 ...
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 ...
1 vote
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 ...
248 views

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 ...
1 vote
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 ...
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$...
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 ...
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 ...
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$ ...
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 ...
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 ...