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

learn more… | top users | synonyms (1)

3
votes
1answer
68 views

An upper bound on the number of sets of parallel lines covering points in a finite plane?

Let $\mathbb{F}$ be a finite field of characteristic $2$. Let $L_m$ denote the set of lines in $\mathbb{F}^2$ with slope $m\in\mathbb{F}$, that is, all parallel lines of the form $y=mx+b$. Consider a ...
1
vote
1answer
166 views

Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier

Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$. Q1. What is the least time complexity possible/known for recreating the ...
8
votes
1answer
955 views

Primes that are the sum of three squares

This is in some sense an extension of the earlier MO question, "Gaussian prime spirals." Gaussian primes in the complex plane, $a+b i$, require $a^2 +b^2$ prime off the axes. The generalization to ...
25
votes
6answers
3k views

Covering a unit ball with balls half the radius

This is a direct (and obvious) generalization of the recent MO question, "Covering disks with smaller disks": How many balls of radius $\frac{1}{2}$ are needed to cover completely a ball of radius ...
25
votes
0answers
518 views
+250

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...
9
votes
0answers
127 views

Self-avoiding random walks that always turn

I am wondering if the statistics of self-avoiding random lattice-walks on $\mathbb{Z}^2$ that turn left or right at each step (i.e., they cannot continue the direction of the preceding step) have been ...
9
votes
3answers
10k views

Dividing a square into 5 equal squares

Can you divide one square paper into five equal squares? You have a scissor and glue. You can measure and cut and then attach as well. Only condition is You can't waste any paper.
17
votes
4answers
1k views

What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs?

This problem was posed in March 2010 at G4G9 in a talk by the Japanese mathematician Hirokazu "Iwahiro" Iwasawa. He claims there is a simple proof that N > 10, though he did not share it with the ...
4
votes
0answers
70 views

How many subspaces are generated by three or more subspaces in a Hilbert space?

In the book of G. D. Birkhoff "lattice theory", it is mentioned that there are 28 subspaces that can be obtained from three subspaces in general position in a Hilbert space (using intersections and ...
1
vote
1answer
117 views

Chern classes of three (two) dimensional complex vector bundles

Let $M$ be a manifold. Let $F(M,3)=\{(m_1,m_2,m_3)\mid m_1, m_2, m_3\in M, m_i\neq m_j, \text{ for any } i\neq j\}$. Let $S_3$ be the symmetric group of order $3$. Let $S_3$ act on $F(M,3)$ by ...
8
votes
1answer
72 views

A variant of Nelson-Hadwiger Problem on the chromatic number of the plane

The famous Nelson-Hadwiger problem asks about the chromatic number of the graph $G$, with the vertex set $V(G)={\mathbb R}^2$ where $a_1=(x_1,y_1), a_2=(x_2,y_2) \in V(G) \ $ form an edge iff ...
3
votes
2answers
465 views

What's the name of this geometric mathematical modeling problem?

There is a right angle corner with width 1 in both directions. One wants to find the largest area shape which can pass through this corner. I know that this is a famous problem, but what is it called? ...
2
votes
0answers
79 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 ...
5
votes
1answer
126 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 ...
9
votes
0answers
228 views

Neighborly family of coins

Here is a puzzle: Find 5 identical coins. Can you arrange them so that every coin is touching every other coin? The solution is here. The hint is: use the third dimension. My questions are ...
1
vote
1answer
30 views

number of affine pieces of linear interpolation of convex functions in high dimension

Consider a convex function $f$ defined on a $d$-dimensional hypercube $[0,1]^d$. Now for fixed $m \in \mathbb{N}$, consider the grids $\mathcal{G}_m=\{(i_1/m,\cdots,i_d/m)\}$ where ...
3
votes
3answers
324 views

Aperiodic graphs

The concepts of being non-periodic and aperiodic for tilings have obvious versions for connected graphs with a countable set of vertices and a finite number of edges meeting at each vertex. A graph ...
3
votes
0answers
85 views

Modeling bubble rafts

If you go to images.google.com and search on "bubble rafts", you'll see various pictures of disk packings that in large patches look like the six-around-one dense packing of the plane by equal-sized ...
3
votes
1answer
285 views

Balancing real numbers in one dimension

Given numbers $0 \leq d_i \leq 1$ for $i=1,\ldots,m$, it is easy to see that you can always find signs $\varepsilon_i \in \{-1,1\}$ such that the partial sums $\sum_{i=1}^k \varepsilon_i d_i/2$, for ...
3
votes
2answers
117 views

regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations

While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...
4
votes
3answers
257 views

Perimeter/Neighborhood of a graph on grid

Hello, I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one. Now I want to claim ...
3
votes
1answer
239 views

Min Bend Orthogonal Knots

I am seeking literature on 3D orthogonal drawings of knots, especially minimum bend drawings. An orthogonal drawing employs segments parallel to the axes of a Cartesian coordinate system. A bend is a ...
13
votes
1answer
343 views

Is the Ford disk packing optimal?

Given two unit-diameter disks tangent to a given line and to each other, determining a region bounded by two circular arcs and a line segment, is the Ford disk packing of that region the unique ...
9
votes
1answer
144 views

Optimal shape for stabbing balls in $\mathbb{R}^3$

I have radius $r < \frac{1}{2}$ congruent balls with centers randomly distributed uniformly within a region, say, within a unit-radius sphere $S$. I shoot a ray/path through $S$, hoping to ...
2
votes
0answers
73 views

Infinite counter-examples to Borsuk conjecture

When I formulate the Borsuk conjecture in the form of a coloring problem, Aigner told me that the formulation is not quite correct: It only works if the set is finite. He's right. All the ...
7
votes
0answers
83 views

Points on $k$ Circles

Let $k$ be a fixed positive integer. We want to find the minimum number $f(k)$, such that for a set of finite points in the plane, if any $f(k)$ of them are on $k$ circles, then all of them are on $k$ ...
12
votes
0answers
250 views

Grothendieck on polyhedra over finite fields

In Grothendieck's Sketch of a Programme he spends a few pages discussing polyhedra over arbitrary rings and concludes with some intriguing remarks on specializing polyhedra over their "most singular ...
1
vote
0answers
69 views

degenerate abelian surfaces

I am wondering if the family of degenerate abelian surfaces constructed by K. Hulek, C. Kahn and S.H. Weintraub in "Moduli spaces of Abelian Surfaces: Compactification, Degenarations, and Theta ...
3
votes
1answer
139 views

Packing bounds for sumsets, or, very discrete balls

Let $D\subset \mathbb{F}_2^n$ with $D=-D$ and $0\in D$. Write $k D$ for the set of all sums of $k$ (not necessarily distinct) elements of $D$. (This is the "ball" in the title.) Now let $d(g,h)$ be ...
1
vote
0answers
75 views

An exact fraction of a matrix

Let $A$ be a $n \times m$ real matrix with $n<<m$ and of rank $r<n$. It is known that $A$ has exactly two distinct non-zero singular values: $\sigma_{\max}$ and $\sigma_{2}$, and also that ...
2
votes
1answer
81 views

Complex lines arrangements from a given wiring diagram

I'm working on some presentation of the fundamental group of the complement of a complex lines arrangement in $\mathbb{C}^{2}.$ In particular, in Arvola's article "The fundamental group of the ...
6
votes
2answers
185 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
votes
0answers
81 views

Can we replace 2-fold cover by n rectangles with 1-fold cover by n rectangles?

Suppose that $n$ rectangles cover every point of their union exactly twice (except for points on their boundaries). Can we partition this union into at most $n$ rectangles? I think it's pretty ...
3
votes
1answer
132 views

Braid wiring diagrams and matroids

recently I started reading some articles about the presentation of the fundamental group of lines arrangements in $\mathbb{C}^{2}$ via Wiring diagrams. I also found some relation with matroid theory. ...
10
votes
1answer
287 views

Soft question: mathematics about truchet tiles

It seems that this is the first question on Truchet tiles on MO. Shown above is a picture of a random tile, which you can see the resulting configuration is much like many membranes of cells. I ...
4
votes
2answers
310 views

How to flip one triangulation on a surface into another

Let $S$ be a compact orientable surface and $p_1,\dots, p_n\in S$ be distinct points. We consider all triangulations on $S$ with vertices $p_1,\dots, p_n$. Is there an algorithm which takes two ...
7
votes
2answers
687 views

Which (semi)regular polyhedra are combinations of two others?

The convex combination of convex polytopes is a convex polytope. An example in $\mathbb{R}^2$ is that a regular octagon can be obtained as $\frac{1}{2} S + \frac{1}{2} S'$, where $S$ is a square and ...
3
votes
2answers
87 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 ...
0
votes
0answers
44 views

Number of faces of polytope projecting to lower dimensional polyhedron

Denote $K=\mathrm{conv}(v_1, \ldots, v_n)\subsetneq\Bbb R^m$ to be convex set spanned by vectors $v_i\in\Bbb R^m$ with $m\leq n$ then what technique could be useful to upper bound minimum number of ...
16
votes
1answer
451 views

Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$, with coordinates $\equiv 2 \bmod 3$, we place, with equal probability, one of these six patterns:       The result ...
3
votes
1answer
166 views

n-dimensional Delaunay Triangulation of Lattices

I have several questions concerning the Delaunay triangulation of a high dimensional lattice. Given an $n$-dimensional lattice $L$ and its Delaunay triangulation (partition of $R^n$ into simplices ...
0
votes
0answers
33 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$. ...
2
votes
1answer
90 views

mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations. Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
1
vote
0answers
145 views

covering high dimensional hypercube by balls

suppose we are given the $d$-dimensional hypercube $H^d$ defined as $$ H^d:=\left\{\sum_{i=1}^d\epsilon_ie_i:\ \epsilon_i\in \{0,1\}\mbox{ for }i=1,\dots , d\right\} $$ and $(e_i)_{i=1}^d$ the ...
8
votes
1answer
111 views

Tilting the $d$-cube to vertically separate its vertices

Let $C_d$ be a unit edge-length cube in $d$ dimensions. I would like to orient it ("tilt" it) so that the vertical (last) coordinates of its $2^d$ vertices are maximally separated, in the sense that ...
2
votes
1answer
307 views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or math.stackexchange. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
11
votes
1answer
286 views

Are all well behaved “mean” functions on $\mathbb{R}^+$ equivalent?

Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties: $M(a,a)=a\qquad$ (identity) $M(a,b)=M(b,a)\qquad$ (commutativity). and possibly ...
4
votes
1answer
216 views

convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...
36
votes
3answers
2k views

Is the “Napkin conjecture” open? (origami)

The falsity of the following conjecture would be a nice counter-intuitive fact. Given a square sheet of perimeter $P$, when folding it along origami moves, you end up with some polygonal flat figure ...