All Questions
Tagged with reference-request discrete-geometry
174 questions
5
votes
2
answers
441
views
Touching-tetrahedra graphs
Have the graphs representable by touching tetrahedra been explored?
Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$
with pairwise disjoint interiors.
Define a graph $G_{\cal T}$ to have ...
- 151k
3
votes
1
answer
159
views
Work on "Churning Polygons"
Background of this question is that I recently stumbled over the problem of deforming polygons in area-preserving way, i.e. modifying the angles between adjacent edges while preserving edge-lengths, ...
- 13.6k
5
votes
1
answer
245
views
What is Known About the Complexity of Calculating Minimal Surface Polyhedra?
I am currently ruminating about ways of generalizing Minimum Spanning Trees to Minimum Spanning "Hypertrees", where the cost is associated with simplex volumes and, where certain topological ...
- 151k
3
votes
3
answers
330
views
Voronoi and Delaunay
Please provide some references on Voronoi and Delaunay decompositions which is mathematically written. I mean I can find several texts or links on this written for computer science students without ...
- 6,337
4
votes
2
answers
506
views
Empty lattice simplex or White's theorem
White has proved (White, G. K. Lattice tetrahedra -- Canad. J. Math. 16 1964 389–396.) the following theorem:
If $T$ is a closed tetrahedron and $\Lambda$ is a lattice which contains the vertices of $...
- 151k
7
votes
1
answer
938
views
Which knots' stick numbers are twice their crossing numbers?
Looking at a table of minimum stick numbers for knots (table here),
it seems the known upper bound of $2 c(K)$ in terms of the knot crossing number $c(K)$
is realized by the trefoil $3_1$—it ...
- 4,713
13
votes
1
answer
430
views
Detecting a hidden convex body with line probes
Imagine that, somewhere inside an origin-centered, unit-radius sphere
$S$ in $\mathbb{R}^3$,
sits a convex body $K$ of volume vol$(K)=\alpha (\frac{4}{3} \pi)$,
with $\alpha < 1$ the fraction of ...
- 151k
6
votes
2
answers
381
views
Lattice-cube minimal blocking sets
Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with
each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$.
Define a blocking set for a lattice cube to be a set of points
in ...
- 151k
4
votes
0
answers
213
views
Counting the polytopes of the translates of the resonance hyperplane arrangement inside the unit hypercube
Let $n$ be a positive natural number. For all $\emptyset \subset S \subseteq \{1, \ldots, n\}$ and $k \in \mathbb{Z}$, define the hyperplane $H(S,k)$ in $\mathbb{R}^n$ given by the equations
$$H(S,k):=...
- 283
17
votes
3
answers
2k
views
Applications of Kirchhoff's circuit laws to graph theory
Is there a good survey on applications of Kirchhoff's circuit laws to graph theory or/and discrete geometry?
Examples:
Matrix tree theorem,
Squaring the square,
Electrician’s proof of Euler’s ...
- 24.2k
11
votes
3
answers
1k
views
Combinatorial distance between simplicial complexes
Let $K_1$ and $K_2$ be two simplicial complexes.
I am seeking a measure of the distance between $K_1$ and $K_2$ when
viewed as combinatorial objects.
What I have in mind is something like this.
...
- 12.5k
11
votes
3
answers
665
views
Limit shape for fixed-perimeter lattice polygons
Let $P$ be a simple polygon defined by $n$ unit-length segments
connecting lattice points of $\mathbb{Z}^2$.
I have two operations that preserve the perimeter of $P$.
The first is the "pop" of a ...
- 22.8k
3
votes
1
answer
292
views
Existence of Simple Closed Straightest Geodesics
There are at least three distinct simple closed quasigeodesics on convex polyhedra [Mat. Sb. (N.S.), 1949, 25(67) :2, 275–306 Quasi-geodesic lines on a convex surface Pogorelov].
Is the same true ...
- 4,713
10
votes
2
answers
930
views
What is determined by the combinatorics of the shadows of a convex polyhedron?
Define the shadow of a convex polyhedron $P$ in direction $u$
to be the orthogonal projection of $P$ onto a plane whose normal is $u$.
The shadow is a convex $k$-gon.
I am wondering to what degree $P$ ...
- 151k
6
votes
1
answer
276
views
Matching on sphere to create cycle with chords
Imagine a number of chords of a sphere $S$ which nearly, but not quite, pass through
the center of $S$, in such a way that no pair of chords intersect:
I would like to ...
- 151k
2
votes
2
answers
676
views
Midpoint lattice polygons
Midpoint polygons (a.k.a Kasner polygons) have been studied, and their behavior is well understood.
I am considering a variant, which I call midpoint lattice polygons.
Start with a sequence of ...
CommunityBot
- 1
10
votes
0
answers
1k
views
Interpolating points with minimum curvature constraint
I have $n$ points $p_i$ strictly interior to a rectangle $R$,
and I would like to connect them with a curve $C$ whose curvature is as low as possible.
Let $\kappa_\max(C)$ be the sharpest (largest ...
- 151k
5
votes
1
answer
265
views
Maximal number of triple intersection points of $n$ circles
It is easy to show that $n$ (mutually different) circles on the plane can have maximum $n(n-1)$ intersection points. In our optimal graph drawing research we have encountered a counterpart of this ...
- 63
24
votes
1
answer
2k
views
Building a genus-$n$ torus from cubes
I wonder if this has been studied:
What is the fewest number of unit cubes
from which one can build an $n$-toroid?
The cubes must be glued face-to-face,
and the boundary of the resulting object ...
- 151k
52
votes
5
answers
2k
views
Tetris-like falling sticky disks
Suppose unit-radius disks fall vertically from $y=+\infty$,
one by one, and create a random jumble of disks above the $x$-axis.
When a falling disk hits another, it stops and sticks there.
Otherwise, ...
CommunityBot
- 1
16
votes
1
answer
1k
views
Random polycube shapes
I am wondering if it is hopeless to obtain any firm results
on the following model of a "random polycube shape."
First, a polycube in $\mathbb{R}^3$
is a connected face-to-face gluing of unit cubes.
(...
- 151k
7
votes
0
answers
187
views
distance distributions on a hypersphere?
Fix a real number $0\leq t\leq 1$ and an integer $n>1$. Let
$\mathbb{S}^{n-1}\subset\mathbb{R}^n$ denote the unit hypersphere. Define
$$d_N(n;t):=\max\sum_{i<j}\Vert P_i-P_j\Vert_2^t$$
where ...
- 43.2k
6
votes
0
answers
118
views
Convex hull of all-ones principal submatrices
For a subset $S$ of $\{1,\ldots,n\}$,
let $\mathbf{1}_S\in\{0,1\}^n$ denote the indicator vector of $S$, with a $1$ on the $i$th coordinate iff $i\in S$. Let $\mathcal{X}$ denote the convex-hull of ...
6
votes
2
answers
424
views
A class of tilings with amazing visual qualities
For more examples please see my related question on MSE:
Interesting tiling with a lot of symmetrical shapes
This is achieved by rotation of square grid over itself by atan(3/4).
Resulting ...
CommunityBot
- 1
4
votes
0
answers
164
views
Two variants of the Littlewood-Offord theorem
I found two different looking things being called the Littlewood-Offord theorem,
If $\vec{a} \in \mathbb{R}^k \setminus 0$ and $t \in \mathbb{R}$ then there are $O(\frac{2^k}{\sqrt{k}})$ points $x \...
- 2,246
4
votes
1
answer
365
views
Orchard-planting problem in space
The original orchard-planting problem asks for the maximum number of $3$-point lines attainable by a configuration of points in the plane. I am interested in its natural generalization for (three-...
- 23.7k
1
vote
0
answers
71
views
Name for a Specific Planar Linear Transformation
Is there a name for linear transformations of the plane, that make $4$ points in general convex configuration co-circular, with the biggest circle through those points and, how can they be determined ...
- 13.2k
2
votes
1
answer
242
views
Smallest angle among two lines in an n × n grid
Does anybody have a reference answering the following (at least for me surprisingly non trivial) question?
Given an $n \times n$ integer grid, what is the minimum angle between any two distinct lines,...
CommunityBot
- 1
4
votes
2
answers
207
views
Classification of symmetries of tilings in surfaces?
Is there a general study of the symmetries of tilings on surfaces?
Conway, Goodman-Strauss & Burgiel classified them on $\mathbb S^2, \mathbb R^2$ and $\mathbb H^2$, with their 'Magic Theorem'. ...
- 561
4
votes
0
answers
143
views
Balanced partitions of vector sets
We are interested in the following
Lemma. Let $V\subset [0,1]^n\subset\mathbb R^n$ be a set of $n$-dimensional vectors. Then for each $r\le |V|$ there exists a partition $$V=V_1\cup V_2\cup\dots \cup ...
- 5,409
5
votes
2
answers
342
views
Minimum length of a convex lattice polygon containing k lattice points?
Let $f(k)$ denote the minimum length of a convex lattice polygon containing exactly $k$ lattice points (including lattice points on the boundary).
It is not too hard to show that $k = \frac{1}{4\pi} ...
- 30.1k
1
vote
0
answers
39
views
Homology of the subcomplexes of the "diamond shaped" sphere under 1-norm in $R^n$ as a simplicial complex
The 1-norm on $\mathbb{R}^n$ is defined by $\|v\| = |v_1| + |v_2| + \cdots + |v_n|$ for a vector $v = (v_1, \ldots, v_n) \in \mathbb R^n$.
The unit sphere $S^{n-1}_1$ under the 1-norm is a simplicial ...
- 19.6k
4
votes
0
answers
158
views
Reference for the notion of polyhedra "degenerations"
Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that:
a) $P(0)=P$;
b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ (...
- 3,513
1
vote
0
answers
77
views
Non-adjacent Pair of Edges with Minimal Weight Sum
Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
is that ...
CommunityBot
- 1
12
votes
2
answers
2k
views
Fold-and-cut problem in three dimensions
The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...
- 151k
5
votes
1
answer
161
views
Upperbounding the number of regions induced by a set of unit disks
Given a set $D$ of $n$ same radius disks, embedded in the plane, their arrangement induces a number $k$ of connected regions in $\mathbb{R}^2 \setminus \cup_{d \in D}$ .
I am interested in an upper ...
- 6,523
3
votes
1
answer
191
views
Maximal $\pi/2$-separated subset of the sphere
A subset $A$ of a metric space is called $\varepsilon$-separated if
$$dist(x,y)> \varepsilon \mbox{ for all } x\ne y\in A.$$
(Notice that the inequality in my definition is strict.)
What is the ...
CommunityBot
- 1
13
votes
1
answer
933
views
Drawings of complete graphs with $Z(n)$ crossings
Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{...
- 10.9k
7
votes
1
answer
216
views
How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?
This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
- 96.4k
3
votes
2
answers
261
views
Examples of toric threefolds
I am looking for examples of smooth projective toric threefolds $\mathbb P_\Delta$ such that the rational polytope $\Delta$ has only pentagonal faces and hexagonal faces.
I quickly searched for ...
- 5,186
3
votes
0
answers
169
views
Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)
Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of $...
- 6,210
6
votes
2
answers
400
views
Geometric dominating set: NP-complete?
Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...
- 4,994
1
vote
0
answers
70
views
Covering number of the range of a function
I have come across the need to know a bound on a certain curious quantity: the covering number of the range of a continuous function $f: D \rightarrow \mathbb{R}^n$, where $D \subseteq \mathbb{R}^m$. ...
- 183
8
votes
4
answers
530
views
Inside-out polygonal dissections
A dissection of a polygon $P$
is a partition of $P$ into a finite number of pieces, which can then be rearranged
(via planar translations and rotations) and joined (without overlap) to form a new ...
- 151k
3
votes
0
answers
391
views
Dissection of a polygon into convex polygons
Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...
- 935
5
votes
1
answer
398
views
Ham sandwich theorem for discrete measures - reference request
A discrete version of the ham sandwich theorem states as follows (see for instance "Common Hyperplane Medians for Random Vectors" - Hill):
For every $\mu_1,...,\mu_n$ discrete (i.e., purely atomic) ...
- 19k
21
votes
5
answers
5k
views
What arrangement of unit cubes minimizes surface area?
For each of these two questions, one can assume that the arrangements are polycubes (for which a definition can be found in the excerpt-image below).
Question A. How does one arrange $n$ unit cubes ...
CommunityBot
- 1
1
vote
0
answers
61
views
Generalizing Concepts of Planar Euclidean Geometry to Symmetric TSP-Instances
To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view.
Examples are:
the diagonals of the convex hull of a set of points in the euclidean plane; ...
- 13.2k
6
votes
1
answer
587
views
Study of convex polytopes via commutative algebra
Let $P \subset \mathbb{R}^d$ be any convex polytope with integral vertices, and let $M$ be the additive submonoid of $\mathbb{R}^{d+1}$ which is generated by $\{ (v,1) : v \in P \cap \mathbb{Z}^d \}$. ...
- 1,046