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

learn more… | top users | synonyms (1)

10
votes
3answers
644 views

Combinatorial analogues of curvature

There appear to be many "combinatorial" definitions of curvature as applied to finite simplicial (or regular CW) complexes. For instance, we have the ideas of Cheeger, Muller and Schrader, of Forman ...
21
votes
1answer
1k 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 ...
13
votes
1answer
500 views

Partitioning the vertices of an n-cube with random hyperplane cuts

An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry. It is an old chestnut of a ...
9
votes
0answers
299 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 ...
3
votes
1answer
260 views

Grading a non-graded poset as squeezed as possible

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage). Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...
21
votes
6answers
2k 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 ...
3
votes
2answers
327 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 ...
2
votes
0answers
129 views

A relation on triplets of points in the plane

This question is a follow up of my previous one (Planar sets closed under intersection of circles, Planar sets closed under intersection of circles) and is motivated by G. Zaimi's answer ...
2
votes
1answer
198 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 ...
1
vote
1answer
110 views

Generalizing the internal angle of a graph in $\mathbb{E}^2$ to $\mathbb{S}^2$

I am currently working on research involving packing problems and am finding myself needing the tools from Combinatorial Geometry (in particular, I've been reading Pach and Agarwal's book on the ...
4
votes
1answer
289 views

Planar sets closed under intersection of circles

Let $P$ be the plane with a point at infinity. By plane, I mean the Euclidian plane, and therefore it has circles. A line is also a circle, though its center is at infinity. If $A\subset P$ has ...
10
votes
2answers
289 views

Acute triangulation

Assume that $S$ is a finite 2-dimensional simplicial complex equipped with a metric $d$ such that each triangle is isometric to a plane triangle (so $(S,d)$ is a polyhedral space). Is it possible ...
45
votes
2answers
2k views

vector balancing problem

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct. This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...
3
votes
1answer
317 views

from affine matroid to measures

Let $S$ be an arbitrary finite spanning subset of $\mathbb{R}^d$ of cardinality $N$. Let $W(S)$ be the formal $\mathbb{R}$-vector space generated by all $d$-dimensional simplices (i.e. bases of the ...
2
votes
1answer
166 views

Lipshitz Constant of the convex extension of a submodular function

The title says it all :) Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function ...
2
votes
2answers
563 views

maximum number of shortest path among a set of n triangle obstacles

Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting ...
6
votes
1answer
313 views

Polygons that are hard to guard

Given an $n$-vertex polygonal 'art gallery' $P$ in the plane, it is possible to cover the interior of $P$ by placing 'guards' at (at worst) $\lfloor n/3\rfloor$ of the vertices of $P$. That this is ...
3
votes
1answer
338 views

Transience of self avoiding random walks on $\mathbb{Z}^d$

I'm finishing up a masters thesis in computer science and want to say a bit in the introduction about self-avoiding walks. My thesis looks at a random process which arose in computer science and my ...
0
votes
1answer
342 views

On the number of lines of given points

Hi all, I have a question Concerning Beck's theorem. I have read it from http://en.wikipedia.org/wiki/Beck%27s_theorem and I have two questions : I suppose Beck's theorem doesn't hold when instead ...
8
votes
1answer
458 views

Triangulations of polytopes and tilings of zonotopes

Consider a set $A = \{ a_1,a_2,\ldots, a_n \} $ of vectors in $\mathbb{R}^d$, which lie in a common affine hyperplane. Two convex polytopes may be obtained from $A$, namely the convex hull of the ...
9
votes
2answers
304 views

The area of the intersection of convex sets with prescribed pairwise intersections

Consider two numbers $a>b>0$. Let $A_1,A_2,A_3$ be three convex sets in ${\mathbb R}^2$ such that $\mu(A_i)=a$, $\mu(A_i\cap A_j)=b$ ($\mu$ is the usual measure on ${\mathbb R}^2$). What is the ...
11
votes
1answer
192 views

Metric conditions on configurations of points with only finitely many solutions

There is an old puzzle, which I believe I learned from Nob Yoshigahara, that asks for all configurations of four (distinct) points in the plane such that the six pairwise distances assume only two ...
8
votes
3answers
626 views

Small 4-chromatic coin graphs

A coin graph is a graph that can be represented by a set of disjoint, except possibly touching, unit disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that ...
10
votes
0answers
276 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 ...
7
votes
1answer
854 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 ...
15
votes
3answers
1k views

Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

What is the best upper bound known on the (absolute value of) the Euler characteristic of a simplicial complex in terms of the number of its facets ? In particular, I am interested in proving or ...
88
votes
5answers
5k views

Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer, moving initially $\pm$ in the horizontal or vertical directions. When it hits a Gaussian prime, it turns left ...
3
votes
2answers
193 views

Form a $\mathbb{Z}^d$ lattice cycle from given lengths

Suppose you are given a list of integer lengths, e.g., $(5,3,2,2,1,1,2,1,1)$. The task is to decide if they can form a closed cycle in $\mathbb{Z}^d$ by connecting segments of those lengths in order, ...
4
votes
2answers
506 views

On the joints problem in finite fields

The original version of the so-called "joints problem" consists of the following: Let $L$ be a set of lines in $\mathbb{R}^{3}$. Determine the maximum number of "joints" determined by these lines, ...
26
votes
2answers
618 views

Careless packing

The sequence $\frac{1}{2}, \frac{1}{2\cdot 2}, \frac{1}{3\cdot 4}, \frac{1}{4\cdot 6}, \frac{1}{5\cdot 8}, \frac{1}{6\cdot 10},\ldots$ has a curious property, as follows: a) the series with these ...
17
votes
2answers
1k views

Erdős-Szekeres for first differences

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however, that we want to find a subsequence which is not ...
17
votes
3answers
701 views

Sperner Lemma Applications

I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of ...
6
votes
0answers
814 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 ...
4
votes
2answers
383 views

Conformal structure does not see conical singularities

the conformal structure does not see the conical singularities of a polyhedral surface. This is a quote from the Preface of Quantum Triangulations (eds.: Carfora, Marzuoli). The sentiment is ...
3
votes
3answers
276 views

Vertex-transitive polytopes in any dimension with any number of vertices?

Given positive integers $d$ and $v$ with $v \geq d+1$, does there always exist a (convex) vertex-transitive $d$-polytope with $v$ vertices? It seems that the answer should be "obviously" true, but I ...
3
votes
1answer
439 views

Tverberg partitions with less than (r-1)(d+1)+1 points

The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap ...
2
votes
0answers
244 views

Erdős-Szekeres empty pseudoconvex $k$-gons

I am wondering if the Erdős-Szekeres empty convex $k$-gon question has a different answer if convexity is replaced by a pseudoline-version of convexity. The empty convex $k$-gon question is a variant ...
10
votes
1answer
514 views

Polygons uniquely inducing arrangements

A beautiful, relatively recent result is that, Every simple arrangement $\cal{A}$ of $n$ lines in the plane is induced by a simple $n$-gon $P$. In a simple arrangement, every pair of lines ...
7
votes
1answer
267 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$. After being open for decades, Francisco Santos has ...
7
votes
3answers
255 views

Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

Let $P_n$ be a "random convex polyhedron" in $\mathbb{R}^3$ of $n$ vertices, where "random" could follow any one of a number of models: (1) the convex hull of $n$ points randomly and uniformly ...
12
votes
1answer
517 views

Ratio of circumscribed/inscribed $(n{-}1)$-gons

As a discrete analog of the MO question, "Löwner-John Ellipsoid: incribed and circumscribed," I've been wondering what might be the maximum ratio of this quantity? Let $P$ be a convex polygon of $n$ ...
26
votes
2answers
893 views

Bodies of constant width?

In two-dimensional case one can generalize figures of constant width as figures which can rotate in a covex polygon. Here is one example which can be used to drill triangular holes: I would like to ...
4
votes
4answers
1k views

Delaunay triangulations and convex hulls

This is a reference request. I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
6
votes
2answers
214 views

convex polytopes with many faces and edges but few cells and vertices

For a convex polytope $P$ in $\mathbb R^4$, denote by $N_0,N_1,N_2,N_3$ respectively the number of vertices, edges, faces, cells. By Euler's formula, we know $N_0+N_2=N_1+N_3$, which means there is a ...
24
votes
2answers
721 views

chromatic number of the hyperbolic plane

A notorious problem in combinatorics is the following: If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required? This ...
7
votes
1answer
207 views

Integer points in dilations of a disk of volume one

The following question is related to When are Ehrhart polynomials polynomials?. For a positive integer $n$, let $i(D,n)$ be the number of integer points in the disk $x^2+y^2\leq n^2/\pi$, so $i(D,n) ...
13
votes
2answers
2k views

How many vertices/edges/faces at most for a convex polyhedron that tiles space?

I wonder if this problem has already been examined before: Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have? ...
1
vote
1answer
386 views

Combinatorial optimization and graph coloring

I am considering the following problem: (i) Fix $n$ and color the edges of $K_n$ red and blue arbitrarily. (ii) Let $M$ be the set of monochromatic triangles in $K_n$ and define $g:M\rightarrow ...
0
votes
0answers
101 views

Question regarding contiguous forms

I read about contiguous forms in Achill Scürmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...
1
vote
0answers
137 views

Traversing perfect quadratic forms

I am wondering whether there is an efficient algorithm to traverse all the $N\times N$ perfect quadratic forms $Q$ inside the polyhedron $e_j^T Q e_j \geq 1$, $j = 1\ldots m$, where $e_j$ are some ...