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

learn more… | top users | synonyms (1)

-3
votes
0answers
76 views

What is a discrete shape [closed]

I saw this term in a paper on tiling using shapes. Can you give the definition for discrete shape? I googled on the web, and could not find any explanation for this concept...
2
votes
1answer
67 views

Measuring the Randomness and Statistics of Convex Polygons

How can I tell, how likely it is, that a given convex polygon with a sufficiently high number of edges is random and, if so, what kind of randomness it is (e.g. white noise)? What is known about ...
1
vote
2answers
150 views

Generalization of Bracketing (or one of its many equivalences)

I asked the following question on MathStackExchange, but I have not received any answers after almost 3 days. Although it may not be a research level question, I thought I could ask it here. *"Is ...
0
votes
0answers
51 views

Colorful version of Fisher's inequality for block designs

Is there such a thing? I am thinking of Karatheodory and Tverberg analogues here.
3
votes
1answer
74 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 ...
1
vote
0answers
45 views

Can any Delone set be approximated by a model set?

Let $\Lambda \subset \mathbb{R}^d$ be a Delone set (uniformly discrete and relatively dense). I would like to know whether $\Lambda$ can be approximated by a model set in the Hausdorff distance. ...
1
vote
0answers
125 views

Find m most distant points from a set of n points [closed]

I would like to find the $m$ (where $n$ $\geq$ $m$ > 1) maximally distant subset of points from a collection of $n$ $d$-dimensional points. Maximally distant means the sum of the pairwise distances ...
6
votes
0answers
171 views

Minimal “basis” in $n$ dimensional unit cube

Let's $$ B^n=\{\bar\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)|\alpha_i\in \{0,1\}\};~~~~n=1,2,\ldots $$ and let's $$ C\subseteq B^n, $$ $$ S(C)=\{\bar\alpha\oplus\bar\beta\ | \bar\alpha,\bar\beta\in ...
6
votes
0answers
102 views

How big can a family of pairwise intesecting affine spaces be?

I apologize if this question might seem to be a bit too elementary. Let $\mathbb{P}^n$ be the projective space over $k$ - an algebraically closed field of characteristic 0. Let $1\leq l\leq n-1$, and ...
-2
votes
0answers
75 views

Minimum distance in unit cube

Given the unit cube $I^n=[0,1]^n$, let $x_1,\cdots,x_n\neq (0,0,\cdots,0)$ be $n$ linearly independent vertices (corners) of $I^n$, and $p(x_1, \cdots, x_n)$ be the projection of $(0,0,\cdots,0)$ onto ...
17
votes
0answers
243 views

Large almost equilateral sets in finite-dimensional Banach spaces

Question: Does there exist a function $C:~(0,1)\to (0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space $X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point set ...
4
votes
1answer
193 views

Panning for gold nuggets: a type of isoperimetric problem

Let $C$ be a unit-radius circle in the plane. Suppose you have a total length $L$ of string available, and your task is to connect chords of $C$ using no more than $L$ of string to minimize the ...
4
votes
1answer
128 views

The Universality Theorem by Mnev for uniform oriented matroids of rank 4 and higher

According to the Universality Theorem by Mnev (see below theorem 8.6.6 from [1]), for any open semialgebraic variety V there is a uniform oriented matroid of rank 3 whose realization space is stably ...
3
votes
1answer
115 views

Three-dimensional Apollonian spirals

Given mutually (externally) tangent spheres $S_1$, $S_2$, $S_3$, $S_4$, let $S_n$ be the unique sphere externally tangent to $S_{n-1}$, $S_{n-2}$, $S_{n-3}$, and $S_{n-4}$ for $n \geq 5$. Let ...
8
votes
0answers
118 views

Randomly placing nonoverlapping unit cuboids

Suppose one places unit cuboids of dimension $d$ with min-corners uniformly distributed to lie in $[0,n]^d$, but with cuboid (strict) overlap forbidden. At some point, the region is "saturated," ...
6
votes
4answers
179 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 ...
6
votes
2answers
226 views

Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...
6
votes
2answers
314 views

Are angles between points enough to decide the realizability?

Let n points in the plane be given whose coordinates we don't know. Assume, however, that for any triple of the points we know the angle. Question: Can we decide whether the n points are realizable ...
7
votes
2answers
375 views

Visibility interpretation of Riemann zeta zeros on the critical line?

This is a long shot, but ... The fraction of $\mathbb{Z}^2$ lattice points visible from the origin $1/\zeta(2)=6/\pi^2 \approx 61$%. The fraction of $\mathbb{Z}^3$ lattice points visible from the ...
2
votes
1answer
64 views

Visibility kernels of embedded graphs

Let $G$ be a connected graph embedded in the plane with all edges straight segments. For $\alpha \in (0,\pi)$, define an $\alpha$-path as a path in $G$ with all turns at vertices within ...
3
votes
2answers
205 views

A problem on chains of squares — can one find an easy combinatorial proof?

Consider the unit square $ S = [0,1] \times [0,1] $. For each $ n \in \mathbb{N} $, we can tessellate $ S $ by the collection $$ A = \left\{ \left[ \frac{i}{n},\frac{i + 1}{n} \right] \times ...
3
votes
1answer
85 views

Points with pairwise integer distances in the plane

Consider $n>3$ points with pairwise integer distances in the plane! What is the relationship between these $n(n-1)/2$ integers? Do we have a theorem or result about these points? Does there exist a ...
6
votes
1answer
217 views

Thinnest 2-fold coverings of the plane by congruent convex shapes

It is an unsolved problem to determine the "thinnest" $2$-fold covering of the plane by disks. The $2$-fold coverage problem by disks is to find the minimum number of congruent (unit-radius) disks ...
3
votes
1answer
49 views

Average vertex degree in finite Delaunay triangulations in high dimensions

In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6. Does anyone know of a similar result in higher dimension? I ...
8
votes
1answer
327 views

Coloring of the plane

I would like to know the minimum number k such that the plane R^2 can be coloured with k colors such that no colour contain all the possible distances. In other words, a colouring such that each color ...
3
votes
0answers
61 views

A taut string of equilateral triangles

Let $T$ be a unit edge-length equilateral triangle composed of three cylinders each of (small) radius $r>0$. (By "small" I mean approximately $< 0.1$.) Think of $T$ as a physical, rigid ...
2
votes
0answers
152 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 ...
4
votes
2answers
109 views

(non-)existence of the aperiodic monotile

The aperiodic monotile problem asks whether there exists a single tile that every tiling made with it results non-periodic. What is known about this problem? If this tile exists, how can it be/not be? ...
7
votes
1answer
137 views

How many maximal triangulations of a rectangle?

I posted the following question on MathStackExchange, but I didn't any answer. So please let me post it on MathOverflow. Let $L_{m,n}\subset\mathbb R^2$ be a rectangle given by $[0,m]×[0,n]$ with ...
28
votes
2answers
562 views

what-if.xkcd.com: stabbing (simply connected) regions on the 2-sphere with few geodesics

In the latest what-if Randall Munroe ask for the smallest number of geodesics that intersect all regions of a map. The following shows that five paths of satellites suffice to cover the 50 states of ...
6
votes
2answers
116 views

Number of edges in linklessly embeddable graphs

Consider graphs over $n$ nodes. What is the maximum number of edges of a linklessly embeddable graph? A more general question is the following. Given $\mu$ what is the maximum number of edges of ...
22
votes
2answers
575 views

Random points on the unit sphere

Suppose you have $n$ points picked uniformly at random on the surface of $\mathbb{S}^d,$ and let the volume of the convex hull of these points be $V_{n, d}.$ Clearly, $V_{n, d}$ converges to the ...
6
votes
2answers
181 views

Pictures of the von Neumann polytope

Are there any graphic portrayals of von Neumann polytopes in low dimensions?
6
votes
1answer
333 views

Groups and pregeometries

Definition. For an infinite structure $\mathcal{A}$ and $cl : P(dom(\mathcal{A})) \longrightarrow P(dom(\mathcal{A}))$ , we say that $(\mathcal{A}, cl)$ is a structure carrying an $\omega$-homogeneous ...
2
votes
1answer
105 views

Distance from constant width bodies

EDIT As @David has observed, my conjecture was clearly wrong for $\ n:=2.\ $ Let me still give it a chance for $\ n\ge 3$. I'll call a family $\ F\ $ of bound closed convex subsets of $\ \mathbb ...
6
votes
1answer
146 views

Minimizing deep holes in sphere packings

What's the current state of knowledge regarding packings of spheres in $n$-space that minimize the supremum of the sizes of the holes? This notion of tightness is more rigid than asymptotic density. I ...
5
votes
1answer
119 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) ...
3
votes
1answer
88 views

Covering points with a shortest lattice spiral

Let $S$ be a finite set of lattice points in $\mathbb{Z}^2$. My question is, roughly: Q. How can a shortest lattice spiral that passes through every point of $S$ be found? A lattice spiral (my ...
9
votes
1answer
230 views

A random variation on Polya's orchard problem

Polya's orchard problem is as follows: "How thick must the trunks of the trees in a regularly spaced circular orchard grow if they are to block completely the view from the center?" See, ...
19
votes
5answers
1k 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 ...
3
votes
5answers
248 views

Approaching convex and discrete geometry from other disciplines

I would like to learn some convex and discrete geometry (number 52 in MSC2010). I thought that it would be interesting to approach it from some other parts of mathematics - either by learning ...
0
votes
0answers
115 views

“Open Points” in the 1983 proof of Szemerédi-Trotter theorem

I was reading through the 1983 paper "Extremal Problems in Discrete Geometry" and I was confused about the definition of "open point" appearing in this paper. By this point in the paper, the authors ...
2
votes
2answers
318 views

Practical use of estimates for the Gauss Circle Problem

This question is related to this and this ones. The Gauss Circle problem asks for the number $N(r)$ of integer points within a sphere of radius $r$ centered at the origin. It is well known that $N(r) ...
7
votes
1answer
92 views

Dropping altitudes to achieve nonobtuse planar triangulations: finite or infinite?

Given a planar triangulation of (say) a convex region, imagine the following process to convert it to a triangulation with no obtuse angles: Pick an arbitrary obtuse angle at vertex $a$ of ...
1
vote
1answer
146 views

Is there a “Bipartite” Szemeredi-Trotter theorem?

One version of the Szemeredi-Trotter theorem states the following: Given a set of $L$ lines in the plane, the number of points incident to at least $k$ lines is bounded above by a constant times $L/k ...
2
votes
2answers
111 views

Maximum possible number of similar three-colored triangles

I want to maximize the number of similar triangles with vertices from three fixed sets, one vertex from each set. For example, if you fix two points $X$, $Y$ (i.e. two sets with only one member), then ...
2
votes
1answer
67 views

Characterization of the medial axis of a surface

I would like to know if the following "characterization" of the medial axis of a surface is correct, and if so, how to prove it. Let $S$ be a continuous, piecewise smooth, compact surface embedded in ...
5
votes
2answers
233 views

Put P inside Q! polygons/polyhedra

We have two Polygons/Polyhedra P and Q. Does there exist a polynomial time algorithm to decide if we can put P (using translation and rotation) inside Q or not? First think about the case of which P ...
10
votes
2answers
490 views

Cut and Fold Polyhedron!

I have two convex polyhedra such that their sums of side areas are equal. It is true that I can cut one of them and flatten it on the plane, then fold the flattened polygon to reach the other ...
5
votes
1answer
198 views

Small remarkable matroids

Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...