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

learn more… | top users | synonyms

4
votes
1answer
114 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
4
votes
1answer
217 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...
3
votes
1answer
40 views

Graph of polytope and hyperplane

Suppose that $P$ is a compact and convex polytope in $R^d$ and let $G$ be the graph of $P$ ($V(G)$ are the vertices of $P$ and $E(G)$ are the $1$-dimensional faces - for example polyedral graphs are ...
2
votes
1answer
43 views

triangulation of the cube of whose vertices are in the set $\lbrace (\pm 1 , \pm 1 , \dots , \pm 1)\rbrace$

Take the cube centered at the origin whose vertices are $\lbrace (1 ,1 , 1) , (-1 ,1 , 1) , (1 ,-1 , 1) , (1 ,1 , -1) , (1 ,-1 , -1) , (-1 ,1 , -1) , (-1 ,-1 , 1) , (-1 ,-1 , -1) \rbrace$. We can ...
6
votes
0answers
51 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
69 views

Regular polygons constructed inside regular polygons

Let $P$ be a regular $n$-gon, and erect on each edge toward the inside a regular $k$-gon, with edge lengths matching. See the example below for $n=12$ and $k=3,\ldots,11$.       Two ...
6
votes
0answers
378 views

Surface integral for a scalar function defined on a discrete surface

Imagine a polyhedral, discrete surface embedded in $\mathbb{R}^3$. Its faces are all triangles. For each vertex, one can compute the discrete mean and Gaussian curvatures and evaluate the sum of ...
6
votes
0answers
138 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
148 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 ...
4
votes
0answers
206 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
274 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 ...
3
votes
0answers
64 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
59 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
81 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)$ ...
3
votes
0answers
108 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
411 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
75 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
23 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
21 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
38 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
70 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
110 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
42 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
77 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
108 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
23 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
16 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
27 views

Center of mass of voronoi cells of 3d lattice

Let $v_1,v_2,v_3$ be linearly independent vectors in $\mathbb{R}^3$, and let $A$ be a matrix whose columns are $v_1,v_2,v_3$. i.e. $A = [v_1,v_2,v_3]$ Then, define a lattice $\Lambda$ as $\Lambda = ...
1
vote
0answers
53 views

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

Given a M x 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 distribution of rectangle ...
1
vote
0answers
29 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
57 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
126 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
60 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
88 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
105 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
25 views

Is there a theory for cellular automata propagating signals in straight lines?

Is there a theory explaining how a cellular automata can propagate signals in straight lines? For example, this video shows how some "signals" travel down at a diagonal, even though they are composed ...
0
votes
0answers
14 views

Why are there only so many Bravais Lattices?

I am in doubt as to why there are exactly five 2d Bravais lattices? For example, I could take the square lattice and place a lattice point at the midpoint on every side of each square. Shouldn't ...
0
votes
0answers
21 views

What does this statement mean exactly?

I would like some clarification about the following from Fejes Toth's paper "A stability criterion to the moment theorem" The setup is: For each positive integer $n$, let $r(H_n)$ and $R(H_n)$ ...
0
votes
0answers
14 views

Plane division by lines

I need help with solving a combinatorial problems. In the plane is m parallel lines. We choose in the same plane n lines, of them no 2 are parallel and each of which are intersecting with given m ...
0
votes
0answers
12 views

Good bounds on non-zero integers assigned to regions of a line arrangement so that sum of integers on each side of each line is 0

Suppose there is a line arrangement in the plane of $n \geq 2$ lines (collection of lines that defines all disjoint positive area subregions with boundaries given by some of the lines), and there are ...
0
votes
0answers
40 views

About Katz centrality

I am studying Graph Theory and Network Analysis, I have this measurement formula which called Katz centrality: My question is: why $A^k$ will grow [infinitely] in $k$ for most cases. As I think ...
0
votes
0answers
23 views

Homomorphisms between countable spaces and Euclidean spaces?

Is there some place to start reading about homomorphisms between countable (discrete) spaces and Euclidean spaces or $l_2$? I know it is a rather general question, but I am not sure what I am looking ...
0
votes
0answers
31 views

Intersection of two convex lattices polygons

A convex lattice polygon is a polygon whose vertices are points on the integer lattice. Let P and Q two convex lattice polygons with n ,(resp. m) vertices. Let R be the convex lattice polygon ...
0
votes
0answers
47 views

Upperbounding the number of regions induced by a set of unit disks

Following up on a previous question: At least as many disks as regions Given a set $D$ of $n$ same radius disks, embedded in the plane, they induce a number $k$ of connected regions in $\mathbb{R}^2 ...
0
votes
0answers
25 views

Laplacian discretization for parametric curves

I know how to compute the discrete Laplacian of a graph and of a mesh (the Laplace-Beltrami operator). Is there an analogous definition for the computation of the Laplacian of a parametric curve ? ...
0
votes
0answers
72 views

Are there any four-dimensional shapes in the whole wide world?

I've looked up images of a 4-D (four-dimensional) shape and they looked like there are built by using regular 3-D (three-dimensional) shapes using a regular 3-D shape connected to another 3-D shape ...
0
votes
0answers
46 views

Constrained optimization using a cutting plane on a tetrahedron

Consider the figure below where $(a,b,c,d)$ is a tetrahedron and $p=(1-t)a+tb$ is a point on the $ab$ segment. If $n_a$ and $n_b$ are two unit vectors associated with $a$ and $b$, respectively, then ...
0
votes
0answers
21 views

Existence objective function given optimality regions

Let $I$ and $X$ be finite, nonempty sets, and denote by $\Delta(X)$ the set of probability measures on $(X,2^X)$. Suppose that for each $i \in I$, we are given a subset $M_i \subseteq \Delta(X)$ of ...