Discrete geometry includes the study of covering, illumination, packing, convex bodies, convex polytopes, and other metric geometry.

learn more… | top users | synonyms

6
votes
0answers
60 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
6
votes
0answers
156 views

Covered 10x10 rectangle with L-shapes trominos

We have given L-shaped trominos and a square of size 10x10. Give a nice proof, that 18 L-trominos is the minimal number with which the square can be covered such that it is impossible to insert one ...
6
votes
0answers
157 views

Unit Distance structure of Hoffman Singleton graph

This question has been bugging me since last 3 years. Prove or disprove that Hoffman Singleton is an unit distance graph in $\mathbb R^2$. For those who are new to unit distance graphs, A graph is ...
5
votes
0answers
32 views

Plane tesselation, using stairs $n\times n$, is it possible?

The other day I was constructing new mathematical problems for my pupils and thought of something like this: Given the infinite sequence of "stairs" $n\times n$, constructed from $1\times1$ ...
5
votes
0answers
366 views

Sphere Covering Problem

Is it possible that one can cover a sphere with 19 equal spherical caps of 30 degrees(i.e. angular radius is 30 degrees)? A table of Neil Sloane suggests it is impossible, but I want to know if anyone ...
4
votes
0answers
97 views

Upper bounds on rate of q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (MRRW) which states that the rate $R(\delta)$ ...
4
votes
0answers
276 views

Tilings of the plane

There are many possible tilings (or tesselations) of the plane: periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings) aperiodic ones by a finite number of prototiles ...
4
votes
0answers
456 views

Parallel transport in discrete differential geometry - programming a game

I would like to get a better intuitive grip on how parallel transport works. I once saw a video a German guy made with a little car having a gyroscope. That car was dragged on a big beach ball and the ...
3
votes
0answers
46 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
3
votes
0answers
33 views

Asymptotic bounds on the number of faces needed to construct a polyhedron of a certain genus

Let a polyhedron be a solid in three dimensions with flat polygonal faces, straight edges and sharp corners or vertices, where moreover we require that every edge touches exactly two faces, every ...
3
votes
0answers
48 views

Elementary proof of Jordan curve theorem for polygons

Courant described the outline of an elementary proof of the Jordan curve theorem for polygons using the order of points: The order of a point $p_0$ is defined by the net number of complete ...
3
votes
0answers
67 views

Number of lines needed to pass through every region of a map

The webpage http://what-if.xkcd.com/113 explores the fewest number of lines needed so that every state in the US has at least one line going through it. (actuallly great circles on a sphere) Can you ...
3
votes
0answers
62 views

Does graphing $ 0 \leq x \leq y \leq z \leq 1 $ and $ 0 \leq x \leq y \leq z \leq \Sigma \leq 1 $ result in a tetrahedron and a pentatope, resp.?

Graph $$ 0 \leq x \leq y \leq 1 $$ Simple. Now Graph $$0 \leq x \leq y \leq z \leq 1$$ Would this simply be a tetrahedron with base shown above and the same triangle in the $yz$ and $xz$ ...
3
votes
0answers
49 views

Optimal way to place a given number of points in a region?

Let $A\subset\mathbb{R}²$ and $n\in\mathbb{N}$ be a given natural number. How to find a finite subset of $A$, $P=${$p_1,...,p_n$} such that $\int_A f_P(x)$ is minimum, where $f_P(x) = ...
3
votes
0answers
112 views

“Round” regions on surface of convex polytope

A convex $d$-polytope $P$ is the convex hull of finitely many points. Given such a polytope with $n \gg d$ vertices, I would like to prove that its surface has to be "round" in some region. Let me ...
3
votes
0answers
79 views

Polytopes-Discrete Geometry

Can someone help me solve the following question please? Let v be a vertex of a d-polytope P such that $ 0 \in intP $ . Prove that $ P^{*} \cap \{ y \in \mathbb{R}^d \mid\left < y, ...
2
votes
0answers
44 views

What is the optimal tiling of a regular n-gon in the plane?

I want to tile the plane with equal-sized regular polygons of $n$ sides. Obviously for some $n$, the tiles will be able to tessellate and cover the whole plane (e.g triangles, squares, hexagons) I ...
2
votes
0answers
42 views

Probabilistic proof for sphere covering upper bound

I would like to show an upper bound for the number of $d$-dimensional spheres needed to cover some closed, bounded subset of $\mathbb{R}^d$, like a cube or another sphere. I could do this by placing ...
2
votes
0answers
29 views

Intersection of a polyhedron and a ball

I'm reading this paper http://www.math.hawaii.edu/~erik/papers/cat0-A.pdf and it looks like I don't get one point. It's the remarks under definition 2.2., mostly the sentence: ,,Imagine a vertex $ x ...
2
votes
0answers
26 views

dimension of Weber set and selectope (as a operator)

Let $\Omega$ be a finite set of players. For a selector $\alpha:(2^{\Omega}-\{\emptyset\})\rightarrow\Omega$, we define a marginal value operator as a linear operator $m^{\alpha}$ ...
2
votes
0answers
46 views

Ehrhart polynomial of lattice tetrahedrons in $\Bbb{R}^4$

Let $\lbrace v_1 , v_2, v_3 , v_4 \rbrace \subset \Bbb{Z}^4$ be linearly independent, and denote by $P$ the convex hull of this set. Now, $P$ is a 3-polytope residing in four-dimensional space. What's ...
2
votes
0answers
80 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
2
votes
0answers
126 views

discrete harmonic extension (an exercise of Grimmett's “probability on graphs”)

I'm struggling with exercise 1.3 in Grimmett's book "probability on graphs". Take $G = (V,E)$ a finite connected graph with given positive conductances $(w_e)_{e \in E}$, and let $(x_v)_{v \in V}$ be ...
2
votes
0answers
47 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 ...
2
votes
0answers
80 views

Combinatorial Laplacian Spectrum

The spectrum of the combinatorial laplacian is well understood for a square lattice. What about for other lattices? In particular: let $ f: \mathbb{Z}^2 \rightarrow \mathbb{R} $. The usual ...
2
votes
0answers
119 views

Twisted tori: discrete and continuous

Taking the advice of Mariano Suárez-Alvarez, I moved this question from MO to MSE: Motivation Let me introduce twisted (discrete) tori: Consider the Cartesian graph product $\mathcal{C}_n = C_n ...
1
vote
0answers
14 views

Lebesgue covering problem's demand for convexivity

Is there a specific reason why in the Lebesgue (universal) covering problem only convex sets are admitted as universal coverings? I see that for any set $X\subseteq{\bf R}^2$ of diameter $\le\alpha$, ...
1
vote
0answers
24 views

On partitioning a finite set of points in the plane by drawing a line

Number of ways to separate $n$ points in the plane The linked answer was to this question: Suppose you have $n$ points in the plane, no two of which are colinear. How do you show that the number of ...
1
vote
0answers
38 views

Covering unit square

Now, I am reading this topic http://mathoverflow.net/questions/34145/can-we-cover-the-unit-square-by-these-rectangles. And do some research on it. Guys, who had written in topics, have said, that they ...
1
vote
0answers
38 views

Simplicial polytope Dehn-Sommerville Equations

Let's suppose we have a polytope P with $dim(P)=d$ and the h vector $ h(P,x)=\sum\limits_{i = 0}^{n} h_ix^{d-i}$ i have to prove that if $h_{k}=h_{d-k}$(simplicial polytope) then $xh(P,x)=h(P,1/x)$ ...
1
vote
0answers
17 views

What is the expected number of edge flips to get from a random triangulation to this special min-max angle triangulation in 2-d?

This comes from a problem my coworker and I are working on, and I'm not sure whether to post it here or MathOverflow or CrossValidated or what. Please let me know if I should migrate the question. We ...
1
vote
0answers
45 views

Is it known whether or not the 'Hauptvermutung' is true for finite simplicial complexes in $\mathbb{R}^4$?

If I have two finite simplicial 4-complexes embedded linearly in $\mathbb{R}^4$ (as in all the lines and faces are straight and flat and there are only a finite number of 4-simplices) do they have a ...
1
vote
0answers
26 views

Polyhedral surface with infinitely many triangulations with same combinatorics

Is there an example of a polyhedral surface that has infinitely many triangulations with the same combinatorics?
1
vote
0answers
22 views

Finitely many hyperplanes separating $ x,y $ in a CAT(0) cube complex

I'm having a great difficulty understanding a proof of a lemma from this paper: http://www.math.hawaii.edu/~erik/papers/cat0-A.pdf It's lemma 1.12. To make it shorter for anyone who'd like to take a ...
1
vote
0answers
72 views

How many distinct area histograms I can get by partitioning a M x N rectangle?

Given a $M \times N$ rectangle $r$, a partition $p$ of $r$ is a collection of rectangles with area smaller or equal than $r$ that cover $r$. The histogram of a partition $h(p)$ is the frequency ...
1
vote
0answers
71 views

Discrete bi-Laplacian

I was wondering whether there exists any kind of literature on the the powers of the discrete Laplacian, in particular the the discrete bi-Laplacian, possibly with weights on the edges. In particular ...
1
vote
0answers
73 views

Krull dimension and Hilbert polynomial of graded rings

Let $P \subseteq \mathbb{R}^n$ be a polytope with integral vertices, and $Q := \mathbb{R}_+ (P \times \{1\}) \cap \mathbb{Z}^{n+1}$ be the monoid of all lattice points of the cone generated by $P$ in ...
1
vote
0answers
151 views

Invertibility of NxN nonnegative matrix with diagonally dominant elements

I have a NxN nonnegative matrix where the diagonal element of any row i is greater than the off diagonal elements, 1 > aii > aij ≥ 0 for j not equal to i . This not a diagonally dominant matrix as it ...
1
vote
0answers
36 views

Weights for degree ordering

Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k\geq 3$. Consider the set $M$ of all monomials of the form $x_1^{i_1}.x_2^{i_2}.x_3^{i_3}$ where each $i_j\in \mathbb{N}$ with $i_j\geq 1$ and ...
1
vote
0answers
64 views

Weighted graphs to minimise the set of distances

$c_{0}$ to $c_{3}$ are given points of the graph and the corresponding weights are $W_{1}$ to $W_{3}$. The objective is to locate $p_{1}$ and $p_{2}$ to minimise the distances $d_{0}+d_{1}$ and ...
1
vote
0answers
91 views

Lipschitz constant of the Laplace-Beltrami operator

I'm reading a paper on discrete differential geometry: Meyer et.al. They define the Laplace-Beltrami operator at a point $P$ by $$\vec{K}(p) = 2k_H(P)\vec{n(P)}$$ where $\vec{n}(p)$ is the normal ...
1
vote
0answers
110 views

Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel. It is clear that by extending the edges of each simple $n$-gon in ...
0
votes
0answers
4 views

Dual of cartesian product of duals of polytopes

I am working on the following problem. Let $P\subseteq \mathbb{R}^d, Q\subseteq \mathbb{R}^e$ be full-dimensional polytopes, both with the origin in the interior. Describe $(P^{\circ }\times ...
0
votes
0answers
17 views

Rotate circle about line if a point on circle is on the line

I'm working with unit-distance graphs in $\mathbb{R}^3$, so all points are in $\mathbb{R}^3$ and points $x$ and $y$ are adjacent (notation: $x \sim y$) if and only if $|x-y|=1$ (where $|x-y|$ denotes ...
0
votes
0answers
13 views

Points on the moment curve form the vertices of the corresponding cyclic polytope

Working through Matousek and I am stuck on exercise 5.4/1a Show that if V is a finite subset of the moment curve, then all the points of V are extreme in conv(V); that is, they are vertices of the ...
0
votes
0answers
6 views

Sufficiently many points in $\mathbb{R}^d$ must contain $m$ points forming the vertices of a convex polytope?

Let us say that a set of points in $\mathbb{R}^d$ is minimal if it forms exactly the set of vertices of a convex polytope. Equivalently, no proper subset of the points has the same convex hull; no ...
0
votes
0answers
24 views

minimal number of sets of binary vectors

I have a set of binary vectors that I would like to group into a minimal number of sets. A set can be formed when it contains all combinations of elements that vary within that set. Example: for ...
0
votes
0answers
6 views

Arrangement of Convex Discs in the plane is independent of the choice of origin?

This is the Problem 3.1 in 'Combinatorial Geometry' by J. Pach, and P. Agarwal. Problem: Prove that if C is any arrangement of convex discs in the plane, then $\bar{d}$$(C,\mathbb{R}^2)$ and ...
0
votes
0answers
14 views

Shelling of a polytope

During line shelling of a convex polytope in d-dimension, it is easy to see that visible facets are shellable. In the same way non visible facets are also shellable. But while combining these two ...
0
votes
0answers
19 views

Number of point subsets defined by a polygon

If $S$ is set of $n$ points in the plane, then $S$ has $2^n$ different subsets. We say that a subset $T\subseteq S$ is "defined by a polygon" if there is a polygon which has $T$ in its interior and ...