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

learn more… | top users | synonyms

2
votes
1answer
38 views

Euler characteristic of closed surface

Assume that you have a closed surface that can be covered by finitely many triangles. Then $K(p)= 6-val(P)$ where P is a vertex and $val(P)$ the number of edges that lead to this vertex. Now, I am ...
0
votes
1answer
29 views

How to define open and closed functions whose domain or range is a discrete metric space?

I encountered that a function is open or closed in my analysis book [Herbert Amann, 2005], and it illustrates it in this way: A function $f: X \xrightarrow{} Y$ between metric spaces $(X,d)$ and ...
0
votes
3answers
28 views

Is there a theorem or axiom which shows that permutations of step sequences through a lattice graph result in the same destination?

I have been searching for a theorem, lemma, or even an axiom which shows that the permutations of a step sequence in Taxicab Geometry result in the same destination in such a lattice graph. To ...
11
votes
2answers
141 views

Partitioning the plane into three sets each intersecting the vertices of every square with side 1?

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? (I mean all squares of side-length 1, not just those with ...
0
votes
1answer
23 views

Prove that a convex $d$-polytope has at least $d+1$ facets

This seems trivial but I can't come up with a formal proof. I think there should be a way to do this inductively but I can't figure out how$\ldots$ Any help much appreciated
0
votes
0answers
19 views

Discrete Geometry (Polytopes)

I have to try to prove the following: Let $V = {v_1,...,v_n} \subset R^d$ be a point configuration affinely spanning $R^d$ (i.e., $aff(V) = R^d)$. Let H be the collection of hyperplanes spanned by ...
0
votes
1answer
17 views

Proof: Minkowski sum polytope implies A and B polytopes

Suppose $A$ and $B$ are convex sets and their Minkowski sum $A+B$ is a polytope. How do you prove that $A$ and $B$ are polytopes as well?
0
votes
0answers
45 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 ...
1
vote
1answer
28 views

Relative Interiors of polyhedra

***Source article: Magnanti, T. L., & Wong, R. T. (1981). Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3), 464-484
2
votes
1answer
33 views

Does a unipotent transformation preserve covolume?

Let $S\subset \mathbb{R}^d$ and define $v(S)$ to be the volume of the set $(S+\mathbb{Z}^d)\cap [0,1]^d$ (where $[0,1]^d$ is the unit cube $[0,1]\times [0,1] \times...\times [0,1]$). Let $T: ...
2
votes
0answers
15 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}$ ...
29
votes
6answers
841 views

Prove Existence of a Circle

There are two circles with radius $1$, $c_{A}$ and ${c}_{B}$. They intersect at two points $U$ and $V$. $A$ and $B$ are two regular $n$-gons such that $n > 3$, which are inscribed into $c_{A}$ and ...
3
votes
0answers
56 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 ...
6
votes
3answers
264 views

On coverings of the complex sphere

Here, everything takes place in $\mathbb{C}^d$ for some $d$, and the sphere $\mathcal{S} = \{\mathbf{x}\in\mathbb{C}^d:\|\mathbf{x}\| = 1\}$. Given $\delta > 0$, consider a collection of vectors ...
0
votes
1answer
18 views

dual set of the dual set

Let $X\subseteq\mathbb{R}^d$ and let $X^*$ be it's dual set i.e. $X^*=\{y\in\mathbb{R}^d| <x,y>\leq 1$ for every $x\in X\}$. How to prove that $(X^*)^*=\overline{conv(X\cup\{0\})}$? I know that ...
3
votes
1answer
105 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
75 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 ...
6
votes
2answers
54 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
30 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
18 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 ...
1
vote
0answers
36 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 ...
2
votes
1answer
32 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 ...
5
votes
1answer
153 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 ...
0
votes
0answers
46 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 ...
2
votes
0answers
33 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 ...
0
votes
1answer
35 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 ...
1
vote
1answer
21 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
65 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
53 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 ...
3
votes
1answer
190 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
1answer
35 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
50 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
42 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}, ...
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 ...
6
votes
2answers
153 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 ...
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
92 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
35 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
31 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
113 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
102 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 ...
0
votes
0answers
37 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
70 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
91 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
175 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
106 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 ...
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? ...
3
votes
1answer
32 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
44 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
55 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 ...