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

learn more… | top users | synonyms

3
votes
3answers
226 views

Cover a cicular hole with planks

A friend of mine asked me the following question. Whats the minimum number of rectangular planks of unit width (and infinite length) needed to cover a circular hole with diameter $n$? ...
0
votes
0answers
14 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 ...
1
vote
1answer
17 views

How to find the center of mass (not vertex average) of a convex hull?

I have found results that say that computing the average of vertices of a polytope presented by inequalities is a #$P$-hard problem. However what if we want the true center of mass (determined by ...
0
votes
0answers
20 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 ...
1
vote
1answer
40 views

finding discrète coordinate of Intersection of two convex polygon?

I seek for cartésien coordinate of vertex's of the intersection area between two polygons ? We have two convex polygon's P & Q such that : all vertex of P (resp. Q) are in 2D cartésien plane. I ...
31
votes
2answers
2k views

Why can't three unit regular triangles cover a unit square?

A square with edge length $1$ has area $1$. An equilateral triangle with edge length $1$ has area $\sqrt{3}/4 \approx 0.433$. So three such triangles have area $\approx 1.3$, but it requires four ...
0
votes
1answer
27 views

What does R^d in last lines refer to

The image above is snapshot in the journal Geometric Approximation http://sarielhp.org/papers/04/survey/survey.pdf via Coresets .I could not figure out what is ...
6
votes
0answers
41 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 ...
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}, ...
1
vote
0answers
49 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 ...
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
1answer
33 views

At least as many disks as regions

I am looking for reference of proof for the following fact: Given a set $D$ of same radius disks, embedded in the plane, it holds that the number of connected regions in $\mathbb{R}^2 \setminus ...
6
votes
0answers
142 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 ...
0
votes
2answers
33 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
3
votes
2answers
63 views

Triangulation of hypercubes into simplices

A square can be divided into two triangles. A 3-dimensional cube can be divided into 6 tetrahedrons. Into what number of simplices an n-dimensional hypercube can be divided? (For example, a ...
0
votes
1answer
30 views

Determining corners of this convex set

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$? Edit: This is apparently true, see the beginning of ...
2
votes
1answer
125 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. ...
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 ...
1
vote
0answers
16 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 ...
0
votes
0answers
22 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 ? ...
1
vote
1answer
44 views

Discrete Gauß and geodesic curvature

Imagine that you have an n-polygon $S$ and you wanted to calculated the discrete Gaussian or gedoesic curvature. How are they defined? If $p$ is a vertex of $S$ then Gauß-Bonnet suggests that the ...
0
votes
1answer
32 views

What is the fundamental theorem on discrete groups of Euclidean spaces?

I have been reading the book Using Algebraic Geometry by David A. Cox, John Little, Donal O'Shea for a university project. I am not clear as to what exactly in meant by the phrase "the fundamental ...
8
votes
4answers
1k views

Definition of simplex

From Wikipedia: an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. I was wondering if the definition is equivalent to say a simplex is synonym of a ...
3
votes
0answers
56 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
39 views

The number of $(d-1)$-faces in a $d$-polytope is at least $(d+1)$

I have to try to prove the following: Let $V = {v_1,...,v_n} \subset \mathbb{R}^d$ be a point configuration affinely spanning $\mathbb{R}$ (i.e., $\operatorname{aff}(V) = \mathbb{R}^d)$. Let $H$ be ...
4
votes
1answer
178 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 ...
1
vote
1answer
25 views
1
vote
1answer
59 views

How Many Triangles are Created by n Lines in the Plane?

Suppose we are given n lines in the plane in "general position", which in the present case we define to mean the following: A. no 2 lines are parallel or identical B. no 3 lines have common ...
10
votes
2answers
169 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 ...
2
votes
1answer
52 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
72 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
37 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 ...
29
votes
6answers
892 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 ...
0
votes
1answer
43 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
57 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 ...
57
votes
4answers
7k views

Why is a circle in a plane surrounded by 6 other circles

When you draw a circle in a plane you can perfectly surround it with 6 other circles of the same radius. This works for any radius. What's the significance of 6? Why not some other number? I'm ...
1
vote
1answer
40 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
35 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
18 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}$ ...
3
votes
2answers
174 views

crossing number question

Prove that there exists constant k such that, for all $5v < e$ there is a subgraph of the complete graph of $v$ vertics with crossing number less or equal than $ k e^3/v^2$. Any hints for a way to ...
3
votes
0answers
59 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
268 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
37 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 ...
4
votes
1answer
160 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
102 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
59 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
20 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
40 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
169 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
169 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 ...