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

learn more… | top users | synonyms (1)

32
votes
0answers
488 views

Extending a line-arrangement so that the bounded components of its complement are triangles

Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that {$L_1,\dots,L_m$} ...
17
votes
0answers
245 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 ...
15
votes
0answers
1k views

Covers of $Z^k$

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ ...
14
votes
0answers
283 views

Knight's tours in higher dimensions

I wonder if Knight's Tours have been explored in higher dimensions, using the following definition of a knight move. In dimension $d=2$, the knight moves left/right and forward/back one step and two ...
13
votes
0answers
2k views

Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?
12
votes
0answers
737 views

Hrushovski's Construction

Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s). Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following: (a) Trivial ...
12
votes
0answers
417 views

Does every connected set that is not a line segment cross some dyadic square?

A dyadic square is a subset of $R^2$ of the form $x + 2^{-n} [0,1]^2$ with $x \in 2^{-m} Z^2$, for integers $m,n \geq 0$. We say that a set $A$ crosses a square $S$ if there exists a connected subset ...
11
votes
0answers
352 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 ...
11
votes
0answers
372 views

Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices? In other words, given any ...
10
votes
0answers
275 views

Update to Shephard's “Twenty Problems on Convex Polyhedra”

Forty-three years ago, Geoffrey Shephard published an influential list of open problems on convex polyhedra. Progress has been made on several of his problems, and perhaps some have been completely ...
9
votes
0answers
296 views

How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

Title question description: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize ...
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," ...
8
votes
0answers
117 views

Diameter of simplicial complex mirrored in property of Stanley-Reisner ring?

Consider a pure finite abstract simplicial complex $\Delta$. Define its diameter as the maximal distance between any two facets, i.e., between any two faces of maximal dimension $d-1$. The distance ...
8
votes
0answers
300 views

A combinatorial approximation functor sSet->qCat

Let $sSet_J$ denote the category of simplicial sets equipped with the Joyal model structure. Simply by the fact that $sSet_J$ is locally presentable and its class of anodynes ($\neq \mathbf{Cof} \cap ...
7
votes
0answers
106 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?

After reading these very interesting questions, I came up with another one: Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
7
votes
0answers
78 views

Is the equidissection spectrum closed under addition?

If a polygon can be cut into $m$ as well as into $n$ triangular pieces of equal area, can it also be cut into $m+n$ triangles of equal area? (I'm editing after realizing that my conjecture that a ...
7
votes
0answers
334 views

Rectangology and squareology

I thought that rectangles were simple, and squares even simpler. Until my research has led me to several questions about rectangles and squares, which I can't solve. I started by posting this ...
7
votes
0answers
140 views

Fractional Helly for more than one piercing

Fractional Helly Theorem says the following: For every $0<\alpha\leq 1$ there exists $\beta = \beta(d, \alpha)$ with the following property. Let $C_1 , C_2 , ..., C_n$ be convex sets in $R^d$, $n ...
7
votes
0answers
228 views

Coloring toroidal polyhedra with convex faces?

Consider a toroidal polyhedron, which is a topological torus, in which all faces are planar, two faces meet in at most an edge, and adjacent faces are not coplanar. The Szilassi polyhedron has 7 ...
7
votes
0answers
590 views

An Ex functor for the contravariant homotopy structure

I'm going to slack on the background and get to the point: Is there a good notion of an $Sd/Ex$ adjunction for $sSet/S$ equipped with the contravariant model structure (cofibrations are monomorphisms ...
7
votes
0answers
269 views

3-dimensional Cayley graph

I would like to see Cayley graphs drawn in 3-dimensional Euclidean space such that the vertices are represented by points and various shadows display the actions of the generators. For example, ...
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 ...
6
votes
0answers
167 views

Linked circles in R3

Two circles in 3-D are linked iff each one passes through the interior of the other. There are $N$ points in 3-D in general position (no four lie on a plane). Each triple of points defines a unique ...
6
votes
0answers
76 views

Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces

Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...
6
votes
0answers
798 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 ...
6
votes
0answers
262 views

A question about a blue fan and a red fan and their common refinement

Is the following conjecture true? Conjecture: Let $M_1$ be a red map and let $M_2$ be a blue map drawn in general position on $S^n$, and let $M$ be their common refinement. There is a vertex $w$ of ...
6
votes
0answers
212 views

balls in arrangements of hyperplanes

The following theorem is from Aronov, Naiman, Pach and Sharir's An invariant property of balls in arrangements of hyperplanes. I would like to state them and then ask if any related problem/theorem ...
6
votes
0answers
454 views

Historical and terminological questions about Dan Kan's Ex functor and its relation to the classical case of simplicial complexes

Recall that we may define a functor $\xi:\Delta\to \operatorname{Poset}$ sending a simplex $[n]$ to the set of monotone injections $[k]\hookrightarrow [n]$ for $k\geq 0$ (effectively, $k\leq n$ as ...
5
votes
0answers
404 views

N-balls covering n-balls

This question is a follow-on question from: Covering a unit ball with balls half the radius The questions are these: Given an arbitrary dimension d, and a unit n-ball in d-dimensional Euclidean ...
5
votes
0answers
434 views

Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and $b$ are natural numbers. For example, this set of ...
5
votes
0answers
310 views

$n$ lines in a general position and the number of empty triangles

Question. Consider $n \geq 5$ lines in a general position (i.e. no two lines are parallel and no triple intersections are allowed) in $\mathbb{R}^2$. Let $T(n)$ denote the maximal number of empty ...
4
votes
0answers
227 views

Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property? Definitions: A subset S of the xy-plane is star-convex if there is ...
4
votes
0answers
119 views

Graph drawing maximizing the volume of the convex hull

Given a graph $G=(V,E)$ and a length function $\ell:E\to\mathbb{R}_+$. An embedding of the graph into the $d$-dimensional Euclidean space is a map $f:V\to\mathbb{R}^d$ such that ...
4
votes
0answers
181 views

Mean number of $n$-simplices per $(n-2)$-simplex in a triangulated $n$-manifold

Work by Tamura (extending results by Luo and Stong) shows the following. Theorem: For any closed 3-manifold $M$ and any rational number $4.5 < r < 6$ there is a triangulation $T$ of $M$ for ...
4
votes
0answers
139 views

Slices of Simplices that are Simplices, Reference?

I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere. Let $A$ be an $l\times n$ matrix with ...
4
votes
0answers
415 views

Intersection of pencils in $\mathcal{R}^2$

Consider $9n$ pencils through non-collinear points $p_1, \ldots , p_{9n}$ in $R^2$ each consisting of at most $n$ concurrent lines. Define the intersection $S$ of these pencils to be the set of points ...
3
votes
0answers
62 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 ...
3
votes
0answers
90 views

Lattices achieving best density

Let $\Lambda \subset \mathbb{R}^n$ be an Euclidean lattice with generator matrix $B$. Define the center density $\delta(\Lambda)$ in the usual way as $\delta(\Lambda) = \rho^n/|\det{B}|$, where $\rho$ ...
3
votes
0answers
122 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 ...
3
votes
0answers
228 views

Tiling a rectangle with weighted cells (min-max problem)

I have been struggling with a research problem. The problem can be formalized as follows: Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ ...
3
votes
0answers
122 views

On understanding Discrete-Valued Stochastic Processes( time series, panel data )

It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...
3
votes
0answers
106 views

What are the Voronoi cones in 4 variables?

Question: What are the top dimensional cones of the 2nd Voronoi decomposition of the space of positive definite forms in $4$ variables? The 2nd Voronoi decomposition of the cone of positive definite ...
3
votes
0answers
87 views

pavings and quadratic forms

Hi, let $L$ be a lattice isomorphic to $\mathbb{Z}^r$ for some positive integer $r$ and $E=L\otimes \mathbb{R}$. An integral paving in $E$ is a set $\Sigma$ of integral polytopes (the vertices are ...
3
votes
0answers
238 views

Coloring $\mathbb{Z}^k$ and a fixed point theorem

This is potentially another approach to this question. I put it as an update there, but perhaps it would be better to post it separately. If we color $\mathbb{Z}^k$ with the $\ell_\infty$ metric in ...
3
votes
0answers
132 views

A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello, What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain $E = \{1,...,n\}$ and a partial function $f: E^3 \to \{-1, 0, 1\}$ ...
3
votes
0answers
232 views

Polygon illumination with perturbed reflections

Here is a variation on the classical polygon illumination problem. For $c \geq 0$ we say that a mirror has reflection index $c$ if whenever a ray hits the mirror with angle of incidence $\alpha$ then ...
3
votes
0answers
125 views

Dimension of convex arrangements for hypergraphs

Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A. Has ...
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 ...
2
votes
0answers
44 views

Looking for N-dimensional spheres in the configuration space of the colorful Tverberg problem

Here we use standard notation for Tverberg's theorem: Dimension $d$, number of partition blocks $r$, and $N=(r-1)(d+1)$. The configuration space of Tverberg's theorem is the simplicial complex ...