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

learn more… | top users | synonyms

1
vote
0answers
21 views

Is every finite group of isometries a subgroup of a finite reflection group?

Is every finite group of isometries in $d$-dimensional Euclidean space a subgroup of a finite group generated by reflections? By "reflection" I mean reflection in a hyperplane: the isometry fixing a ...
1
vote
2answers
48 views

Calculating volume of spherical wedge from parallelepiped corner

I am interested in calculating the volume of the intersection of a sphere of radius 1/2 with the corner of a parallelepiped where the angles between each edge is $\pi/3$ and has unit edge length; we ...
5
votes
2answers
50 views

Simplest graph that is not a segment intersection graph

Given a finite collection $S=\{s_1,s_2,\ldots,s_n\}$ of straight-line segments in the plane, their intersection graph $G(S)$ is a graph that contains a vertex $v_i$ for each segment $s_i\in S$, and an ...
0
votes
0answers
16 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 ...
0
votes
0answers
19 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 ...
3
votes
1answer
121 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 ...
1
vote
1answer
123 views

Schlegel diagram of polytope

I'm currently studying polytopes and using the book Lectures in Geometric Combinatorics by Thomas. When I come to Schlegel diagrams, I do not quite understand how to determine whether a Schlegel ...
1
vote
0answers
23 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 ...
5
votes
1answer
134 views

The lattice points of a f.g. rational cone form a f.g. monoid.

In their book "Polytopes, Rings, and K-Theory" Bruns and Gubeladze sketch an alternative approach to Gordan's Lemma, which is stated in the headline (f.g. = finitely generated). I don't understand the ...
2
votes
1answer
19 views

Smallest triangle in a convex polygon triangulation

I have been working on this problem for quite a while and it seems necessary to prove or disprove this particular problem. Suppose $T$ is the set of all possible triangles made from the vertices of a ...
3
votes
1answer
184 views

Algebraic proof of Ehrhart's theorem

Let $P \subset \mathbb{R}^d$ be a $d$-dimensional polytope, where all vertices lie on integral coordinates, and let $L(P,n)$ denote the number of integral lattice points contained in the scaled ...
0
votes
0answers
34 views

A continuous centerpoint of a convex spherical polygon

In discrete geometry, a centerpoint $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a centerpoint always ...
5
votes
2answers
122 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 ...
0
votes
1answer
30 views

Small remarkable matroids

I'm working on a problem involving matroids $M=(E,\mathfrak{C})$ (here $E$ is the ground set, $\mathfrak{C}$ the set of circuits) with a "small" ground set $E,$ in the sense that $\sharp(E)\leq7$ I ...
2
votes
0answers
28 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 ...
1
vote
1answer
20 views

Wrong formulation of Helly's theorem

In Lectures on Discrete Geometry, Matousek writes (p.11) (excerpt here): It is very tempting and quite usual to formulate Helly's theorem as follows: "If every $d+1$ among $n$ convex sets in ...
1
vote
1answer
35 views

Carathéodory's convex hulls theorem and Radon partitions

Wikipedia's article about Radon's theorem and its related states: Carathéodory's theorem states that any point in the convex hull of some set of points is also within the convex hull of a subset ...
1
vote
1answer
49 views

Topological subspace in $(S^{1})^{n}$

Studying the set of solutions of a particular linear system associated to a matroid, I notice that is it possibile to determine the topology of the quotient and identify it as a subtorus of ...
0
votes
1answer
29 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$. ...
5
votes
0answers
43 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 ...
1
vote
1answer
41 views

Volume of a parallelopiped

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}, ...
6
votes
2answers
136 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
0answers
34 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 ...
0
votes
0answers
11 views

About the logistic map.

I need guide line about it I also wanted to know how it will appear in graph if we use mathematica or some other software for this.
2
votes
1answer
89 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
28 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
30 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.
3
votes
1answer
31 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
90 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
81 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 ...
3
votes
1answer
132 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 ...
0
votes
0answers
33 views

A configuration of 4 points on the plane that minimizes the variance of the distances between the points

This is connected to my earlier question: Embedding finite (discrete) metric spaces to Eulidean space as isometrically as possible but now I'm only considering the smallest (non-trivial) case. We ...
2
votes
1answer
62 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 ...
3
votes
0answers
81 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
26 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? ...
1
vote
1answer
98 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 ...
1
vote
2answers
37 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
1answer
55 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 ...
2
votes
0answers
48 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 ...
4
votes
0answers
98 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
270 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 ...
0
votes
1answer
90 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 ...
1
vote
1answer
74 views
11
votes
1answer
428 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 ...
1
vote
2answers
649 views

Distinct Hamiltonian cycles of the icosahedron and dodecahedron

I am seeking a listing of the distinct Hamiltonian cycles following the edges of the icosahedron and the dodecahedron. By distinct I mean they are not congruent by some symmetry of the icosahedron or ...
0
votes
1answer
105 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
45 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
48 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 ...
2
votes
0answers
82 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
84 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 ...