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

learn more… | top users | synonyms

2
votes
2answers
54 views

How to determine a kind of distance between two permutations?

Let's define a distance between two permutation of length $N$: it is the minimum steps to change one to be another. "A step of change" means that exchanging any two elements' location. For example, ...
0
votes
1answer
15 views

Lattice points in simplices - reference request

I found this paper http://homepages.math.uic.edu/~yau/35%20publications/An%20upper.pdf which, in formulas (1.2) and (1.3), relates the number of non-negative and positive integer values that are ...
7
votes
1answer
51 views

Partitioning $\mathbb{R}^d$ with two convex sets

The problem/puzzle is: Find two convex sets in Euclidean space, $A, B\subseteq\mathbb{R}^d$, such that the number of connected components of $\mathbb{R}^d\setminus (A\cup B)$ is the maximum ...
20
votes
5answers
1k views

Pick's Theorem on a triangular (or hex) grid

Pick's theorem says that given a square grid consisting of all points in the plane with integer coordinates, and a polygon without holes and non selt-intersecting whose vertices are grid points, its ...
1
vote
0answers
32 views

Is it known whether or not the 'Hauptvermutung' is true for finite simplicial complexes in $\mathbb{R}^4$?

If I have two finite simplicial 4-complexes embedded linearly in $\mathbb{R}^4$ (as in all the lines and faces are straight and flat and there are only a finite number of 4-simplices) do they have a ...
0
votes
1answer
35 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 ...
4
votes
1answer
98 views

One special case of Helly's theorem (for $\text{radius}=1$ circles)

There are $n$ points on the plane. Any $3$ of them can be covered with a radius $1$ circle. Prove that there is a radius $1$ circle that covers all the points. Came to this when tried to prove an easy ...
1
vote
1answer
32 views

Nearly-unit-distance graph (UDG) density

Q1. How dense can a nearly-unit-distance graph be? Let points sit in $\mathbb{R}^2$. A unit-distance graph UDG "connect[s] two points by an edge whenever the distance between the two points is ...
6
votes
0answers
113 views

Balanced, center-free set. [closed]

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say ...
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?
0
votes
0answers
16 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 ...
5
votes
2answers
132 views

Convex polyhedron and its Gauß-curvature

I am trying to prove: A convex polyhedron has positive Gauß-Curvature at every vertex. What we know: Gauß-Curvature at every vertex is given by $K(p) = 2\pi - \sum\limits_{\text{angle } ...
1
vote
1answer
16 views

Is optimal bound for Alcuin's triangular city problem known?

Alcuin's triangular city problem is Problem 28 from Propositiones ad Acuendos Juvenes. There is a triangular city which has one side of 100 feet, another side of 100 feet, and a third of 90 ...
2
votes
1answer
48 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 ...
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)$ ...
2
votes
2answers
1k views

Mean distance between N equidistributed points in a circle

I would like to calculate the mean distance depending on circle shape points, This is a mean for calculating all possible distances between any two points for $N=2$, line, there is only 1 distance. ...
61
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 numbers? I'm ...
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 ...
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 ...
0
votes
0answers
16 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 ...
1
vote
0answers
29 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 = ...
6
votes
2answers
46 views

Which planar angles on an integer lattice are possible?

As shown in this question, you can construct an angle $A$ on 3 integer points on a plane only if $\tan A$ is rational. A natural generalization is to ask which values can planar angles based on 3 ...
0
votes
1answer
59 views

upper bound and a lower bound on the number of points that are uniformly distributed on a surface

Can I calculate an upper bound and a lower bound (or max or min) on the number of points that are uniformly distributed on a surface, knowing the area of the surface ? More precisely, I have a sector ...
0
votes
0answers
41 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 ...
3
votes
3answers
282 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
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 ...
1
vote
1answer
57 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
35 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
67 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 ...
34
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
31 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
54 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
50 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
56 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
48 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
37 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
149 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
38 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
84 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
154 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
117 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
31 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
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 ? ...
1
vote
1answer
69 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
39 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 ...
9
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
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$ ...
1
vote
1answer
45 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 ...