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

learn more… | top users | synonyms

0
votes
1answer
42 views

2D discrete Jordan curve theorem: what about the “boundary points”?

Let us say we have a polygon $P$ in $\mathbb{R}^2$, with edges in the set $E$ (the boundary), and vertices in the set $V$. Let us say we have a point $Q$ such that $Q$ lies on one of the edges in $E$. ...
6
votes
0answers
62 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 ...
2
votes
1answer
49 views

Volume of a parallelepiped

Suppose $\Lambda$ is a lattice in $\mathbb{R}^n$ of rank $r$ and $\mathbf{b}_1, ..., \mathbf{b}_r \subseteq \mathbb{R}^n$ its basis. I know that if we pick any orthonormal vectors $\mathbf{e}_{r+1}, ...
2
votes
0answers
35 views

Squaring the plane with consecutive integer squares. And a related arrangement. [duplicate]

Q1. I was fiddling around with squaring-the-square type algebraic maths, and came up with a family of arrangements of $n^2 $squares, with sides $1,2\ldots n^2$ (n odd). Which seems like it would work ...
6
votes
2answers
185 views

Squaring the plane, with consecutive integer squares. And a related arrangement

Q1. I was fiddling around with squaring-the-square type algebraic maths, and came up with a family of arrangements of $n^2$ squares, with sides $1, 2, 3\ldots n^2$ ($n$ odd). Which seems like it would ...
2
votes
1answer
99 views

Question related to a determinant of lattice

There is this equation related to the determinant of lattice and I have been stuck on it for a little while. I would greatly appreciate if someone could explain to me how to prove it! Let $\Lambda$ ...
0
votes
1answer
40 views

Is mean pairwise distance a metric over subsets of a metric space.

Specifically, I am looking at finite subsets of a set that is a discrete metric space under Jaccard Distance. I'm having trouble proving the triangle inequality or coming up with a counterexample. ...
0
votes
1answer
34 views

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs?

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs? I would really appreciate for any kind of explanations.
2
votes
1answer
149 views

Geometry textbook

I am planning to take a graduate Geometry course next semester. The preliminary syllabus does not specify any textbook but has the following descriptions: Catalog Course Description: This course ...
1
vote
0answers
121 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 ...
2
votes
1answer
81 views

Embedding finite (discrete) metric spaces to Eulidean space as isometrically as possible

Let $X = \{1, 2, 3, ..., k\}$ with the discrete metric (distance is 1 for every pair of points). How can this be embedded into $\mathbb{R}^n$ (with the usual metric) such that the embedding would be ...
4
votes
1answer
110 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 ...
3
votes
1answer
224 views

Poisson point process (PPP) and Voronoi cells

Say we have a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. In one realization of the PPP we get the points $\phi=\{x_1,x_2,...,x_i,...\}$. Now we generate the Voronoi cells ...
1
vote
1answer
130 views

Cover the n-sphere with sub-hemispherical caps

Original Question (answered): Define a cap (x,Phi) to be the set of all points of the sphere that are within an angle Phi of the point x. $ 0 \le \phi < \frac{\pi}{2} $. (define the angle ...
2
votes
1answer
36 views

Cyclic polytope of dimension 4

I don't quite know how to count the number of $k$-dimensional faces of a $4$-dimensional cyclic polytope (http://en.wikipedia.org/wiki/Cyclic_polytope) without using the standard formula. Any advice? ...
3
votes
1answer
37 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 ...
1
vote
2answers
52 views

Proof for the length of the shortest 4-connected path and 8-connected path on a chessboard

I have a chessboard with a square marked with A as in the following figure: $$\begin{array}{|c|c|c|} \hline 8&1&2\\ \hline 7&A&3\\ \hline 6&5&4\\ \hline \end{array}$$ The ...
2
votes
0answers
65 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 ...
3
votes
1answer
172 views

Tetromino Proof

Prove that an 8 x 8 board cannot be covered by 15 L-tetrominos and one square tetromino (an L-tetromino is a plane figure shown below, constructed from four unit squares arranged in the form of L; a ...
2
votes
1answer
72 views

Reference for important results in linkage theory and their proofs

Are there books or lecture notes that comprehensively introduce the (geometric/topological) theory of mechanical linkages, as well as important results and their proofs? For instance, Kempe's ...
4
votes
1answer
192 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 ...
6
votes
0answers
349 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 ...
3
votes
0answers
57 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$ ...
1
vote
1answer
95 views

If we spot n dots on a sphere (radius r), there exists two dots whose distance is under d

Is there any formula about $n$, $r$, $d$ at the question?
0
votes
1answer
97 views

Question related to Desargues' Theorem

The diagram below is one way of drawing two triangles ($\Delta PQR,\ \Delta P'Q'R'$) perspective from a point ($O$), with pairs of corresponding sides meeting at $D, E, F$ as in Desargues' Theorem ...
12
votes
1answer
464 views

Circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them

I have a serious problem with this problem: Is it possible to Draw circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them !? Any help ...
0
votes
1answer
107 views

Flip graph of point set [closed]

Is the flip graph of every point set in $\mathbb R^3$ connected? If not, is there a set with an isolated node? Def: For a point set $S$, the flip graph of $S$ is a graph whose nodes are the set of ...
2
votes
1answer
47 views

Filling Ratio of Unit Sphere

Consider the unit sphere $S^n$ in ${\bf R}^{n+1}$. Consider $S(r)$, a union of $r$-balls in $S^n$ which is disjoint and that $S(r)$ has maximum area. Then define $$ c_n\doteq ...
2
votes
1answer
131 views

Intersection of line with discrete hypercubes in n-dimensional space

I am looking for a method to determine the hypercubes that intersect a line between two points in a high dimensional space. I think what I want is the supercover of a line in high dimensional space. ...
2
votes
1answer
92 views

halving lines through the centroid of a cyclic polygon

Let $A_1, A_2,\ldots, A_{2n}$ be $2n$ points on a circle centered at $O$ with the additional property that the centroid of this set of points coincides with $O$. In other words, the sum of the vectors ...
6
votes
0answers
135 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 ...
5
votes
2answers
143 views

Regular Pentagon is the Unique Largest Two-Distance Set in the Plane

A two-distance set is a collection of points for which only two distinct distances appear among pairs of points. (That is, the distance between any pair of points is either $x$ or $y$, and these ...
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 ...
7
votes
1answer
130 views

Helly's Theorem for Biconvex Sets

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
26
votes
4answers
588 views

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
2
votes
0answers
107 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
1answer
54 views

Simplex with edges of length at least s having smallest circumradius

Is it true that of all $k$-simplices with edge lengths greater than or equal to some parameter $s$, the regular simplex with edge lengths $s$ has the smallest circumradius? Please supply a proof or ...
3
votes
1answer
60 views

Simple geometry problem on distribution of points in a plane

Consider 6 distinct points in a plane. Let $m$ and $M$ be the minimum and maximum distances between any pair of points. Show that $M/m \ge \sqrt3$. I am more interested in arrangement of these points ...
1
vote
2answers
99 views

Approximating Euclidean geometry, restricted to $\mathbb{Q}$

I'm having trouble putting this into a fully coherent question, so I'll give the broad question, then a few bullet points to give you a better idea of what I'm asking. I'm looking for a line of ...
1
vote
0answers
59 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 ...
2
votes
2answers
114 views

Discretizing continuous surfaces into semi-regular polygons

I am aware that there have been many works on the problem of discretizing a surface into polygons, however, I wonder if in any work the problem of doing so to get polygons with edges of the same ...
6
votes
0answers
143 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
3answers
274 views

Dissecting an equilateral triangle into equilateral triangles of pairwise different sizes

It is know that a square can be dissected into other square such that no two of the squares have the same size. This is the simplest dissection of that kind: Is it also possible to dissect an ...
0
votes
1answer
41 views

Number of faces of $n$ congruent disks

If I have $n$ disks, all of the same radius, how many faces (i.e. maximally connected regions) can the induced arrangement have? For example for 3 disks, it could have 7 bounded faces, but what is ...
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 ...
1
vote
1answer
143 views

example that shows that the edge chromatic number may be larger than the maximal degree

What is an example that shows that the edge chromatic number may be larger than the maximal degree ∆ ≤ X’(G)
0
votes
1answer
34 views

Elementary doubt about derivations on Jacobians

Hi I have a small doubt on Discrete Geometry, more specifically the derivation of Jacobian. Say we have a function $x:\mathbb{R}^2\supseteq U \rightarrow \mathbb{R}^3 : (u,v) \mapsto x(u,v)$ Also ...
2
votes
0answers
75 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 ...
3
votes
0answers
48 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) = ...
7
votes
3answers
288 views

Name this polytope

I was wondering what people call a certain type of shape. It is the shape formed by an orthogonal projection of a hypercube along one of its longest diagonals. In other words, fill in the missing ...