Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

1
vote
0answers
46 views

Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?

General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
0
votes
0answers
27 views

How many points are still contained in a common (hyper-)ellipsoid?

It is known that $${d+2\choose 2}-1$$ points uniquely determine a quadric in $\Bbb R^d$. However, I want my points not on an arbitrary quadric, but on a centered hyperellipsoid in $\Bbb R^d$, or ...
5
votes
0answers
102 views

Polychromatic number of plane

Let $\chi$ be the least size of a partition of plane into pieces each of which omits unit distance. Let $\chi_p$ be the least size of a partition of plane into pieces each of which omits some distance....
2
votes
1answer
169 views

Name and Algorithms for a Sparsest Circle Packing

The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...
-4
votes
0answers
46 views

Combinatorial geometry [closed]

We call a point P inside a triangle ABC marvelous if exactly 27 rays can be drawn from it, intersecting the sides of ABC such that the triangle is divided into 27 smaller triangles of equal areas. ...
5
votes
0answers
98 views

How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?

Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...
6
votes
2answers
207 views

Visual proof of convergence for Steiner's symmetrization

I want to find a visual proof of the following fact: For any convex figure in the plane there is a sequence of Steiner's symmetrizations that makes it arbitrary close to a circular disc. All ...
6
votes
0answers
95 views

Tiling with incommensurate triangles

Say that two triangles are incommensurate if they do not share an edge length or a vertex angle, and their areas differ. Suppose you'd like to tile the plane with pairwise incommensurate triangles. I ...
8
votes
2answers
197 views

Counting Hamiltonian cycles in $n \times n$ square grid

I wonder if anyone has counted these curves, either exactly or asymptotically? Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$ lattice points: a lattice square. Define a ...
3
votes
0answers
169 views

Shapes defined by points

Can shapes determined by number of points? From an amazing theorem in plane curves geometry we know that vertices of triangles similar to arbitrary triangle $T$ is dense on every closed jordan curve ...
4
votes
2answers
124 views

Counting points and lines in a plane

Let $P_1$ be a set of 4 points in the Euclidean plane. Formally, $P_1$ determines a set $L_1$ of 6 lines, which then determine only 3 points not already in $P_1.$ Let $P_2$ be the set of 7 points ...
1
vote
3answers
195 views

Repeatedly halve and twist a planar shape: Limiting shape?

Consider the following iterative process. Start with a planar region $R=R_0$ of $\mathbb{R}^2$. I am thinking of $R$ as connected, but it may become disconnected. In the example below, $R$ starts as ...
15
votes
1answer
231 views

Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
5
votes
2answers
161 views

The number of co-circular four tuples

Let $A,B ⊂ \mathbb{R}$ such that $|A| = |B| = n$. What is the best-known upper bound on the number of four-tuples in $A \times B$ where the four points are co-circular, they lie on the same circle?
1
vote
1answer
75 views

Coloring lines in plane

We assume that all the lines in the plane are each colored with one of two colors: red or blue. Given angle $\alpha.$ My question 1. Is there possible to get two lines with the same color and angle ...
7
votes
0answers
82 views

Counting symmetric convex bodies with no nonzero lattice point in the interior

In order to estimate the size of the torsion in the algebraic $K$-groups of $\mathbb Q$ one needs to understand the homology of $\mathrm{GL}_n(\mathbb Z)$, or alternatively, the homology of the space ...
0
votes
1answer
79 views

Positioning a member of an interval partition

Let $\ 0<\Lambda_1\le\ldots\le\Lambda_n\ $ be a finite non-decreasing sequence of positive reals, of length $\ n>0.\ $ Let $$ D:=\sum_{k=1}^n \Lambda_k $$ The question is about the conditions ...
10
votes
0answers
97 views

A combinatorial proof of the Harrow--Kolla--Schulman theorem

Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$. For integers $0 \leq k \leq n$, define a ...
0
votes
0answers
29 views

Realisation of a Polytope as a convex set [duplicate]

Suppose I have ALL the combinatorial data of an abstract Polytope: a list of all facets and incidence relations. Is there a way to produce linear functions, in a suitable $R^d$, so that the region ...
27
votes
1answer
620 views

Four circles on the sphere

Consider configurations consisting of 4 distinct circles on the sphere. Two configurations are equivalent if they can be mapped onto each other by a homeomorphism of the sphere. How to enumerate/...
6
votes
2answers
153 views

Sliding through a curvature-bounded tube: Maximum volume?

My 1st question has a straightforward answer but I'd appreciate hints on a proof. My 2nd question is open from my point of view. Q1. Is it the case that the maximum convex volume body inside a ...
3
votes
1answer
188 views

Density of a somewhat random set

The density of a set $X\subseteq\omega$ refers to: $\limsup\limits_{n\rightarrow\infty}\dfrac{C\cap n}{n}$. Given a set of positive integers $F= \{m_0<\cdots<m_{k-1}\}$, let $C\subseteq \omega$...
22
votes
1answer
405 views

Tying knots via gravity-assisted spaceship trajectories

Q. Can every knot be realized as the trajectory of a spaceship weaving among a finite number of fixed planets, subject to gravity alone?           To make this more ...
3
votes
0answers
648 views

Puzzle in 3D grid with black and white boxes, related to shelling

Consider a $n$ by $n$ by $n$ grid represented by the set of $3$-uples $S=\{1,2,\dots, n\}^3$. A line (resp. slice) of $S$ is a subset of cardinal $n$ (resp. $n^2$) where two components (resp. one ...
3
votes
0answers
48 views

Separating stars and large intersections of cycles

Let $\Gamma$ be a finite simplicial graph. For every $k \geq 0$, let $C_k(\Gamma)$ denote the graph whose vertices are the induced cycles of $\Gamma$ and whose edges link two cycles if their ...
1
vote
1answer
87 views

Number of distinct points in an n-dimensional tetrahedron

Consider an n-dimensional tetrahedron with $n+1$ vertices $\langle v_0, v_1, \dots,v_n\rangle$. $v_0$ is the origin while $v_i$ lies on $e_i$ (the $i^{th}$ coordinate axis) at a distance $D$ from the ...
7
votes
2answers
136 views

How different can the constituents of an Ehrhart quasi-polynomial be?

Consider a $d$-dimensional convex rational polytope $P\subset\mathbb{Q}^d\subset\mathbb{R}^d$. Then, it's a standard fact that in general the function counting the number of lattice points inside the ...
3
votes
0answers
69 views

Number of hypercube unfoldings

While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...
5
votes
0answers
194 views

Almost monochromatic point sets

There are many sort of equivalent theorems about monochromatic configurations in finite colorings, such as Van der Waerden, Hales-Jewett or Gallai's theorem, the latter of which states that in a ...
4
votes
2answers
73 views

How many dihedral angles need to be specified to uniquely specify a triangulated polyhedron?

Suppose you are given a simplicial complex $K$ homeomorphic to the sphere and for each each edge of the complex a label specifying a length of that edge (this gives us a polyhedral metric on $K$). In ...
1
vote
0answers
43 views

How do the 3d models of the hypercube nets relate to the pairings?

In "Unfolding the Tesseract" Journal of Recreational Mathematics, Vol. 17(1), 1984-85. (Journal link.), Peter Turney presents the pairings of an unfolded tesseract. In "3D Models of the Unfoldings of ...
3
votes
1answer
98 views

Size of a minimal non-negative conic basis

Suppose $v_1,\dots,v_n \in \mathbb{R}^k$ are entry-wise non-negative (column) vectors with $k<n$. Let $r \leq k$ be the non-negative rank of the matrix $V = [v_1 v_2 \cdots v_n]$ (i.e., the ...
9
votes
2answers
453 views

Parallelepiped is defined by the volumes of its faces

Let $v_1,...,v_n\in \mathbb{R}^n$ be linearly independent. The parallelepiped defined by these vectors is $P(v_1,...,v_n)=\{\sum_{i=1}^{n}\alpha_i v_i|~0\le\alpha_i\le 1\}$. Observe that while the ...
0
votes
0answers
116 views

What breaks down in the theory of affine hyperplane arrangments?

It appears to me that there is a substantial amount of combinatorial algebra and geometry supporting the theory of central hyperplane arrangements (See Topics in Hyperplane Arrangements, Aguiar and ...
8
votes
2answers
201 views

Graph planarization via rewiring

Let $G$ be a nonplanar graph (undirected) of $n$ nodes and $e$ edges, with $e \le 3n-6$. Define a rewiring move as replacing edge $(a,b)$ with edge $(a,c)$. The result must be a simple graph (no loops,...
6
votes
1answer
271 views

Bichromatic pencils

A pencil is a collection of some lines through a point, called the center of the pencil. If the points of the plane are colored, then call a pencil bichromatic if there is a color that is present on ...
2
votes
1answer
151 views

Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?

Sorry the title may be unclear. I do not know how to give it a good title..... Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
5
votes
0answers
135 views

Question related to high dimensional kissing number

I have a question related to the kissing number in $n$ dimension. Suppose we have many non-overlapping $n$-dimensional balls of radius $1/2$. We place one of the $1/2$-radius ball centered at the ...
21
votes
0answers
486 views

How much of the plane is 4-colorable?

In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
3
votes
1answer
53 views

Unbalanced version of incidences between points and unit circles

Let $P$ be a set of $n$ points and let $C$ be a set of $n$ unit circles, both in $\mathbb{R}^2.$ The maximum number of incidences between P and C is $O(n^{\frac{4}{3}}).$ Is there any bound known for ...
4
votes
1answer
83 views

Szemerédi–Trotter type problem

Given $n$ points and an integer $k ≥ 2.$ What is the maximum number of unit circles which pass through at least $k$ of the points? I think the answer is $O(n^{4/3}/k),$ but I'm not really sure. Any ...
5
votes
0answers
162 views

Longest simple path through hypercube corners

This is a variation on a previously answered question, Longest path through hypercube corners. Here I am seeking the longest simple (non-self-intersecting) path through the unit hypercube's vertices, ...
12
votes
4answers
667 views

Longest path through hypercube corners

Is the longest Hamiltonian path through the $2^d$ unit hypercube vertices known, where path length is measured by Euclidean distance in $\mathbb{R}^d$? The unit hypercube spans from $(0,0,\ldots,0)$ ...
3
votes
1answer
100 views

Question arise from kissing number in 2 dimension

I'm considering an extended problem of kissing number in $\mathbb{R}^2$. Suppose I have a given disc $\mathcal{D}$ of radius 1/2 and infinitely many discs all of radius 1/2 and all these discs and ...
6
votes
1answer
187 views

Szemerédi–Trotter theorem

Szemerédi–Trotter theorem asserts that given $n$ points and $m$ lines in the plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is: $O((mn)^{\...
6
votes
1answer
105 views

Combinatorial curvature of real projective plane

There is a notion of combinatorial curvature due to Forman, see here (published paper) or here (preprint). I checked for a couple of small triangulations of $\mathbb{RP}^2$ (6-vertex, 7-vertex, 9-...
9
votes
0answers
123 views

Interactions between pseudoline arrangements and braid groups?

It is common to represent pseudoline arrangements as wiring diagrams:                     Fig. from: "Hamiltonicity and colorings of arrangement ...
6
votes
0answers
123 views

Sets of points avoiding small angles

(1) $\mathbb{R}^2$. I'd like to place $n$ points in the plane so that the smallest angle they determine is as large as possible. In a sense, such a point set is in very general position, not only ...
3
votes
0answers
151 views

What is a natural way to extend a function from a subset of vertices to faces?

Let $n$ be a positive integer, and suppose $f$ is a probability distribution on the $2^n$ subsets of $[\![n]\!] := \{1,\ldots,n\}$. What is a "natural" way to extend $f$ to a distribution $\bar{f}$ on ...
2
votes
0answers
51 views

Enveloping a Jordan curve with a trace of another one

This question is inspired by this one, or rather the way I understood it. Let $\gamma$ and $\delta$ be parametrised Jordan curves on the plane (i.e. homeomorphisms from $S^1$ onto its image in $\...