Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
1,825
questions
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
0
votes
0
answers
34
views
Convex 3d bodies for which all planar sections with max diameter have same diameter
Ref:
1.
A claim on planar sections of 3D convex bodies
On convex 3d bodies whose shadows are all of constant diameter
Given a 3D convex body $C$ and a specified direction $n$, we consider the planar ...
- 5,493
3
votes
0
answers
92
views
On convex 3d bodies whose shadows are all of constant diameter [closed]
We add a bit to More on shadows of 3D convex bodies
By a shadow of a 3D body, we mean the orthogonal projection of it onto a 2D plane.
If all shadows of a convex 3D body have the same diameter, will ...
- 5,493
10
votes
1
answer
490
views
A projective plane in the Euclidean plane
Problem. Is there a subset $X$ in the Euclidean plane such that $X$ is not contained in a line and for any points $a,b,c,d\in X$ with $a\ne b$ and $c\ne d$, the intersection $X\cap\overline{ab}$ is ...
- 40.9k
0
votes
1
answer
49
views
On largest convex m-gons contained in a given convex n-gon where m < n
This post is the inside-out variant of On smallest convex m-gons that contain a given n-gon where m<n
Given a convex n-gon region P, and an m less than n, how to find the max area convex m-gon Q ...
- 5,493
1
vote
0
answers
121
views
The number of incidences between points and parabolas on $\mathbb{R}^2$
I was reading Adam Sheffer's book "Polynomial Methods and Incidence Theory" and I tried to solve the following exercise:
Exercise 1.1 Construct a set $\mathcal{P}$ of $m$ points and a set $\...
- 298
0
votes
0
answers
89
views
On smallest convex m-gons that contain a given n-gon where m<n
Given a convex n-gon region P, and an m less than n, will the least area convex m-gon Q that contains P be such that an edge of Q coincides with an edge of P (in other words Q cannot be such that P ...
- 5,493
1
vote
0
answers
49
views
On points in the interior of planar convex regions and inscribed triangles
Given any planar convex region C, it is easy to show that every point in the interior C is the mid point of at least one chord of C. Likewise,
Question: Is every point in the interior of C the ...
- 5,493
1
vote
0
answers
46
views
Locality and restriction properties for self-avoiding and loop-erasing random walks
This question has been cross-posted from math.stackexchange.com : https://math.stackexchange.com/questions/4742746/locality-and-restriction-properties-for-self-avoiding-and-loop-erasing-random-wa
I ...
- 541
11
votes
1
answer
660
views
A variant of the corners problem
Question: What is the size of the largest subset of $[n]^2$ containing no three point configurations of the form $(x,y), (x,y+d), (x+d,y')$ with $d \neq 0$? In particular, is it at most $O(n)$?
Recall ...
- 530
1
vote
1
answer
70
views
When do the centers of mass of a uniform convex planar region as a whole and of its boundary alone coincide?
Given a uniform planar convex region C, let us consider 2 centers of mass - the center of mass of the region as a whole and the center of mass of its boundary alone (assuming its boundary to have ...
- 5,493
0
votes
0
answers
170
views
Equivalent formulation of Szemerédi-Trotter theorem
I am reading the first chapter of Adam Sheffer's book "Polynomial Methods and Incidence Theory" and in Lemma 1.15 he proves an equivalent formulation of Szemerédi-Trotter theorem. Before ...
- 298
6
votes
0
answers
124
views
Have the affine simplicial line arrangments been enumerated?
I am looking for a classification (or attempt at enumeration) of affine simplicial line arrangements.
A line arrangment is a family of straight lines in $\Bbb R^2$. It is simplicial if all regions are ...
- 12.6k
8
votes
2
answers
477
views
Continuous point map for spherical domains
Consider the space $J$ of Jordan domains on the sphere $\textbf{S}^2$, i.e., continuous injective maps from the unit disk into $\textbf{S}^2$ modulo homeomorphisms of the disk. How can one construct a ...
- 7,047
2
votes
1
answer
129
views
Planar convex region maximizing the difference in 'orientation' between its smallest containing rectangle and largest contained rectangle
We say a rectangle has orientation $\theta$ if the vector from its center to the middle of its shortest side (parallel to the longest side) has some angle $\theta$ with X axis.
Consider a planar ...
- 5,493
1
vote
1
answer
78
views
To optimally wrap convex laminae with paper
Ref: On folding a polygonal sheet, Multi-layered wrapping of polyhedra
Basic intent: to wrap a given convex planar lamina with a convex sheet of non-stretchable paper (such that every point on both ...
- 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
8
votes
3
answers
803
views
Alternating Sum Involving Catalan Numbers
I was wondering if anyone knew how to obtain a simpler closed form of the following sum(or had any other insights regarding it):
$$\sum_{k=0}^n (-1)^k{n \choose k} C_{2n-2-k} $$
Here $C_n = \frac{1}{n+...
- 449
1
vote
0
answers
158
views
Membership test of convex set
Let $K$ be a compact convex subset of $R^n$ which has some positive gaussian measure, say at least 1/2. For each nonzero vector $u \in R^n$, we
define another compact convex set $K * u$ in the ...
- 11
3
votes
0
answers
73
views
A claim on planar sections of 3D convex bodies
Ref: More on shadows of 3D convex bodies,
Shadows and planar sections of polyhedra
Given a 3D convex body C, we define a maximal area (perimeter) section of C with respect to any specified direction $...
- 5,493
2
votes
0
answers
109
views
More on shadows of 3D convex bodies
Ref: Shadows and planar sections of polyhedra
By shadow we mean the orthogonal projection of a convex 3D body C onto a 2D plane, for example, the shadow on the xy-plane, with C above (z>0) that ...
- 5,493
5
votes
1
answer
146
views
Beating trivial bound for $k$-AP-free sets in characteristic $k$
Given integers $k,n\ge 1$, I shall write $\Bbb{Z}_k^n := (\Bbb{Z}/k\Bbb{Z})^n$.
Fix $k\ge 3$. Let $r_k(\Bbb{Z}_k^n)$ denote the cardinality of the largest $A\subset \Bbb{Z}_k^n$, such that $A$ does ...
- 3,413
2
votes
1
answer
74
views
On convex solids with all plane sections affine congruent
Question: How many (classes of) convex 3D solids are there such that all non-degenerate planar sections of the solid are mutually affine congruent?
Further question: Same as above with 'projective' ...
- 5,493
2
votes
1
answer
76
views
Calculating a relaxed Delaunay Triangulation
The triangles of a planar Delaunay Triangulations are essentially characterized by the property that no triangle's corner is inside another triangle's circumcircle; Delaunay Triangulations can be ...
- 12.7k
1
vote
2
answers
104
views
A claim on concurrency of 'Width Bisectors' of planar convex regions
We add a bit to A claim on the concurrency of area bisectors of planar convex regions
Define a width of a planar convex region $C$ as the distance between two parallel lines that just touch $C$. A ...
- 5,493
2
votes
0
answers
96
views
Real-isability of a (relatively small) subconfiguration of the Klein configuration
The Klein configuration consists of $60$ points and $60$ planes in $\mathbb C\mathbf P^3$, each point lying on $15$ of the planes and each plane containing $15$ of the points. It appears, among many ...
- 17.5k
1
vote
0
answers
64
views
Intercept theorem in $\mathbb R^n$
The celebrated intercept theorem(also known as Thales's theorem) provides the ratios between the line segments created when two parallel lines are intercepted by two intersecting lines.
I'm looking ...
- 193
1
vote
0
answers
34
views
On partitioning convex polygonal regions in area ratio $t : (1-t)$ where $0<t<1/2$ with least length of cut
Question: Given a convex n-gon P. How can we efficiently find the partition of P into 2 pieces with areas in the some given ratio $t : (1-t)$ where $0<t<1/2$ such that the length of cut is ...
- 5,493
1
vote
2
answers
109
views
Are there variants of Euclidean Steiner Tree problem that are known to be in P?
Question: The Euclidean Steiner Tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem) is NP hard. Are there non-trivial (constrained) variants of this question that are known to have ...
- 5,493
8
votes
2
answers
751
views
Three-dimensional triangulations with fixed number of vertices
My question is the following:
Are there triangulations of $S^3$ which (a) are non-degenerate, (b)
have four vertices, and (c) have no edges of degree two?
A side question:
If one represents this ...
- 75
0
votes
0
answers
45
views
Pigeonholing for Slopes
I am reading arxiv from Rudnev and Stevens https://arxiv.org/pdf/2005.11145.pdf. I am stucked in the proof of proposition 1. First, they prove we cannot have $Q_B\leq N^2\tau^2/8$ for at least $50$% ...
- 231
0
votes
1
answer
143
views
Which simplicial complexes are completely determined by the 1-skeleton of their dual polyhedral complexes?
Consider the following line of reasoning that shows certain simplicial complexes (of arbitrary dimension) are completely determined by corresponding graphs:
The facet complex of any simplicial ...
1
vote
0
answers
44
views
Discreteness of $D^{-1}D$ given that $D$ is uniformly discrete
Let $G$ be a topological group with unit element $e$.
We say that $D\subseteq G$ is discrete if for all $x\in D$ there is a unit-neighborhood $U\subseteq G$ such that $x^{-1}D\cap U=\{e\}$. We say ...
- 111
1
vote
1
answer
83
views
Is every triangulation the projection of a convex hull
Question:
given the triangulation $T$ of a set $P$ of $n$ points $p_1,\dots,p_n$ in the euclidean plane whose convex hull is a triangle, can we always find a set $Q$ of $n+1$ points $q_0,q_1,\dots,q_n$...
- 12.7k
1
vote
0
answers
48
views
On families of lines that cut the boundary of a planar convex region in a specified ratio
We proceed from A claim on the concurrency of area bisectors of planar convex regions
This question is somewhat broad.
Background: 'Mathematical Omnibus' by Fuchs and Tabachnikov, Lecture 11 describes ...
- 5,493
1
vote
1
answer
69
views
Partitioning polygons into obtuse isosceles triangles
Ref:
Partitioning polygons into acute isosceles triangles
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
https://math.stackexchange.com/questions/1052063/...
- 5,493
11
votes
0
answers
163
views
Worst margin when halving a hypercube with a hyperplane
Consider the $n$-cube $C_n=\lbrace-1,1\rbrace^n$ and the problem of partitioning it into halves with hyperplanes through the origin that avoid all its points. We can parameterize the hyperplanes by ...
- 1,065
2
votes
0
answers
100
views
Sequence of numbers related to line-segment intersections
Question:
what is known about the sequence $\mathbb{X}\subset \mathbb{N}_0$ such that for each $k\in \mathbb{X}$ there exists a set of $n$ points in general position in the Euclidean plane such that ...
- 12.7k
7
votes
1
answer
239
views
Decidability of completing Penrose tilings
Is the following problem known to be un/decidable? Problem: Given a finite configuration of Penrose tiles in the plane, determine if there is an extension of the configuration tiling the whole plane.
- 449
0
votes
0
answers
23
views
Piecewise affine-isometric maps of polytopal graphs into the plane
There are well-known "relatively faithful" representations of the polytopal metric subgraphs $C^n\subseteq\mathbb R^n$ (with the euclidean distance, for all $n\geq 0$) of hypercubes into the ...
- 972
1
vote
0
answers
65
views
Convolutions of (m)-associahedra and (m)-noncrossing partition polynomials--combinatorial proofs?
I'm looking for combinatorial proofs of the convolutional identity COP below and its specializations I) and II).
(Edit 6/2/2023: A combinatorial proof is sketched in a blog post by Mike Spivey of a ...
- 9,931
0
votes
0
answers
38
views
Centralness of planar convex regions - behavior under projective transformations
Background:
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\...
- 5,493
0
votes
0
answers
40
views
Cutting convex polygons into affine-equivalent quadrilaterals
We continue from Tiling the plane with quadrilaterals that are mutually non-congruent and affine equivalent
Question: Can any convex polygon $C$ be partitioned into some finite number $m$ of ...
- 5,493
0
votes
1
answer
93
views
Tiling the plane with quadrilaterals that are mutually non-congruent and affine equivalent
Question: Can the plane be tiled with convex quadrilaterals that are (1) mutually non-congruent in a Euclidean sense and (2) mutually affine-equivalent?
Remark: Every trapezoid is affine equivalent to ...
- 5,493
0
votes
0
answers
22
views
Reference on high dimensional polytopes with E8 symmetry
I'm starting to work with high dimensional polytopes. I am interested in uniform polytopes of 16-dimension and of 8-dimension (especially Elte and Gosset polytopes that have E8 symmetry).
...
- 295
2
votes
0
answers
92
views
Trapezoid-free subsets of the plane obtained by deleting lines
Let $A,B,C \subseteq \mathbb{Z}_n$. Suppose that for any $a' \in A, b' \in B, c' \in C$,
\begin{align*}
|(A+b') \cap (B+a') \cap -C| &\le 1,\\
|(A+c') \cap -B \cap (C+a')| &\le 1,\\
|-\hspace{-...
- 530
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
1
vote
0
answers
58
views
Covering a unit square with odd number of equal area triangles - optimally
We add a bit to this post: Cutting off odd numbers of equal area triangles from a unit square
Question: Given an odd integer n, how does one cover the unit square completely with n equal area ...
- 5,493
0
votes
0
answers
42
views
Covering triangles with mutually congruent planar regions - optimally
We continue from this old post: From a given triangle, to cut 2 mutually congruent convex pieces that together 'use' maximum area of the triangle and go from partitioning to covering.
Given ...
- 5,493