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
60 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
115 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
146 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
278 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
49 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
293 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 ...
1
vote
3answers
638 views

Proving by induction that an equilateral triangle will always be divided into (n+1)^2 small triangles?

I'm working on a proof that looks like this: Let $n$ be a positive integer. Given an equilateral triangle, place $n$ points on each side, dividing the side into $n+1$ equal segments. Use the ...
1
vote
1answer
185 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 ...
6
votes
2answers
169 views

Voronoi Diagrams Proof

I am having a real problem with this proof about voronoi diagrams: Prove that $V(p_i)$ (i.e., the cell of $\operatorname{Vor}(P)$ which corresponds to $p_i$) is unbounded if and only if $p_i$ is on ...
3
votes
0answers
81 views

Upper bounds on rate of q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (MRRW) which states that the rate $R(\delta)$ ...
4
votes
0answers
201 views

Tilings of the plane

There are many possible tilings (or tesselations) of the plane: periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings) aperiodic ones by a finite number of prototiles ...
2
votes
0answers
107 views

Twisted tori: discrete and continuous

Taking the advice of Mariano Suárez-Alvarez, I moved this question from MO to MSE: Motivation Let me introduce twisted (discrete) tori: Consider the Cartesian graph product $\mathcal{C}_n = C_n ...
1
vote
1answer
117 views

Unit Distance Problem Formulated as Point-Circle Incidence Problem

The unit distance problem in the plane asks for the maximum number $U(n)$ of unit distances which can be obtained by $n$ points. For $k$ unit circles and $m$ points in the plane, $I(k,m)$ counts the ...
0
votes
0answers
69 views

Brouwer’s fixed point theorem ⇒ Sperner’s lemma [duplicate]

Possible Duplicate: Equivalence of Brouwers fixed point theorem and Sperner's lemma Does anyone know a combinatorial proof of the implication from Brouwer’s fixed point theorem to ...
2
votes
2answers
186 views

Triangular grid with 4 edges per vertex

I am trying to create a triangular grid/mesh for a rectangular domain in $\mathbb{R}^2$ with the property that each vertex is shared by (at most) four edges. Is this possible to accomplish?
2
votes
1answer
183 views

Brouwer's fixed point theorem implies Sperner's lemma

I'm looking for a proof that Brouwer's fixed point theorem implies Sperner's lemma. The proof should be understandable by an undergraduate. Thanks in advance!
4
votes
0answers
266 views

Sphere Covering Problem

Is it possible that one can cover a sphere with 19 equal spherical caps of 30 degrees(i.e. angular radius is 30 degrees)? A table of Neil Sloane suggests it is impossible, but I want to know if anyone ...
3
votes
1answer
137 views

Can all convex polytopes be realized with vertices on surface of convex body?

Each convex polytope $P$ has a combinatorial type, its so-called face lattice. This lattice is just the poset of all faces of $P$ ordered by inclusion. Given one realization of such a combinatorial ...
3
votes
0answers
108 views

“Round” regions on surface of convex polytope

A convex $d$-polytope $P$ is the convex hull of finitely many points. Given such a polytope with $n \gg d$ vertices, I would like to prove that its surface has to be "round" in some region. Let me ...
4
votes
3answers
329 views

Average degree of convex hull vertices in a Delaunay triangulation

Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
0
votes
1answer
97 views

A lemma regarding cones covering $\mathbb{R}^d$

Added: Pointers to some references with the same conclusion as the wolloing lemma may be helpful to understand it, and are appreciated. In A Probabilistic Theory of Pattern Recognition By Luc ...
3
votes
0answers
404 views

Parallel transport in discrete differential geometry - programming a game

I would like to get a better intuitive grip on how parallel transport works. I once saw a video a German guy made with a little car having a gyroscope. That car was dragged on a big beach ball and the ...
29
votes
1answer
1k views

Dividing a square into equal-area rectangles

How many ways are there to tile an $n\times n$ square with exactly $n$ rectangles, each of which has integer sides and area $n$? The sequence $C(n)$ begins 1, 2, 2, 9, 2, 46, 2, 250, 37. Clearly ...
3
votes
3answers
232 views

Help me name or find the existing name for this geometric concept!

This may have a proper name, if so - let's discuss. If not, let's name it. This is for a web application in C#, so whatever we call it I will start naming as such in my code. I'm taking GPS data as a ...
4
votes
1answer
130 views

Convex hull of $n$-gon and $m$-gon

Suppose you have a convex $n$-gon, and a convex $m$-gon, in the plane. Take the convex hull of the $n+m$ vertices. How many combinatorially distinct hulls can be obtained, where two hulls are ...
6
votes
1answer
705 views

Intersection of squares/cubes/hypercubes.

One can form a polygon of $4 n$ sides by intersecting $n$ congruent squares (treated as closed sets, i.e., filled squares):          Q1. For which of the ...
3
votes
0answers
75 views

Polytopes-Discrete Geometry

Can someone help me solve the following question please? Let v be a vertex of a d-polytope P such that $ 0 \in intP $ . Prove that $ P^{*} \cap \{ y \in \mathbb{R}^d \mid\left < y, ...
1
vote
1answer
123 views

Restricted Cube Packing

I want to pack n cubes in 3-space under the following 3 restrictions: 1) At each vertex only 2 cubes may touch 2) No two cubes may share an edge 3) No two cubes share any subface 2,3 just mean ...
1
vote
1answer
99 views

Maximum number of points with a fixed minimum distance in a $d$-dimensional ball

Let $c \leq r$ be real numbers greater than $0$, $d \in \mathbb{N}$ and $B_r(0) = \lbrace x \in \mathbb{R}^d \mid \Vert x \Vert \leq r \rbrace$, the ball with radius $r$ at point $0$ ($\Vert \cdot ...
3
votes
2answers
175 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 ...
9
votes
4answers
1k views

Every polygon has an interior diagonal

How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon. In ...
4
votes
3answers
129 views

What is the name of this property?

If there are 3 intervals, such that any 2 of them intersect, then all 3 of them intersect. For any 4 disks, if any 3 of them have a non empty intersection, then all 4 of them have a common ...
5
votes
3answers
244 views

Number of point subsets that can be covered by a disk

Given $n$ distinct points in the (real) plane, how many distinct non-empty subsets of these points can be covered by some (closed) disk? I conjecture that if no three points are collinear and no four ...
3
votes
2answers
271 views

Find center of circle of radius $r$ that overlaps exactly $\lfloor \pi r^2 \rceil$ points of the integer grid

Can a circle of a given radius $r$ always be placed (in $\mathbb{R}^2$) such that the number of points with integer coordinates inside the circle is equal to the nearest integer of the circle's area? ...
3
votes
1answer
165 views

Intersection of Disks

If I have a disk $d$ where each point of the disk is contained in at least $k$ other disks, then at least how many other disks does $d$ intersect? Given, that all the disks (including $d$) have the ...
0
votes
1answer
77 views

$n$ points in disk, determine number of close distances

If I have a disk of radius $r$, and $n$ points inside this disk, I'm interested in the minimum number of distances $\leq r$ between the points, when the minimum is taken over all $n$ point sets in ...
2
votes
1answer
86 views

How to calculate number of lumps of a 1D discrete point distribution?

I would like to calculate the number of lumps of a given set of points. Defining "number of lumps" as "the number of groups with points at distance 1" Supose we have a discrete 1D space in this ...
1
vote
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. ...
8
votes
1answer
371 views

“Center-of-Mass” of lattice polygons (generalization of Pick's theorem)

Call a polygon with integer coordinates (in the Euclidean plane) a 'lattice polygon'. Pick's Theorem allows you to efficiently compute the number of lattice points inside this polygon given just its ...
4
votes
1answer
392 views

Which internal angles can a lattice polygon have?

I am wondering if for a lattice polygon an internal angle can take any value? If no which ones not and why? I guess there will be some restrictions due to the discrete nature of the grid but I am ...
2
votes
2answers
208 views

Cover n points with n disjoint unit disks

This is a problem I saw on Peter Winkler's column on communication of the ACM(might be under a pay wall). It is open. What is the largest $n$, such that you can always cover a given set of $n$ points ...
1
vote
0answers
88 views

Lipschitz constant of the Laplace-Beltrami operator

I'm reading a paper on discrete differential geometry: Meyer et.al. They define the Laplace-Beltrami operator at a point $P$ by $$\vec{K}(p) = 2k_H(P)\vec{n(P)}$$ where $\vec{n}(p)$ is the normal ...
1
vote
1answer
85 views

Cutting a d-simplex

Why is it possible to get any possible subset of nodes of a d+1 simplex in IR^d using halfspaces?
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 ...
4
votes
1answer
605 views

Applications of Morse theory

Background The use of tools from algebraic topology to study simplicial complexes coming from point cloud data has been thoroughly discussed in the papers of Carlsson, Zomorodian, Ghrist, ...