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

learn more… | top users | synonyms

11
votes
1answer
435 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 ...
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
0answers
86 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
85 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 ...
6
votes
0answers
105 views

Covered 10x10 rectangle with L-shapes trominos

We have given L-shaped trominos and a square of size 10x10. Give a nice proof, that 18 L-trominos is the minimal number with which the square can be covered such that it is impossible to insert one ...
5
votes
2answers
124 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 ...
1
vote
0answers
35 views

Weights for degree ordering

Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k\geq 3$. Consider the set $M$ of all monomials of the form $x_1^{i_1}.x_2^{i_2}.x_3^{i_3}$ where each $i_j\in \mathbb{N}$ with $i_j\geq 1$ and ...
0
votes
0answers
34 views

Helly's Theorem for Rectangles

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
7
votes
1answer
123 views

Helly's Theorem for Biconvex Sets

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
23
votes
4answers
506 views

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
1
vote
0answers
98 views

discrete harmonic extension (an exercise of Grimmett's “probability on graphs”)

I'm struggling with exercise 1.3 in Grimmett's book "probability on graphs". Take $G = (V,E)$ a finite connected graph with given positive conductances $(w_e)_{e \in E}$, and let $(x_v)_{v \in V}$ be ...
2
votes
1answer
49 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 ...
3
votes
1answer
55 views

Simple geometry problem on distribution of points in a plane

Consider 6 distinct points in a plane. Let $m$ and $M$ be the minimum and maximum distances between any pair of points. Show that $M/m \ge \sqrt3$. I am more interested in arrangement of these points ...
1
vote
2answers
95 views

Approximating Euclidean geometry, restricted to $\mathbb{Q}$

I'm having trouble putting this into a fully coherent question, so I'll give the broad question, then a few bullet points to give you a better idea of what I'm asking. I'm looking for a line of ...
1
vote
0answers
55 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
98 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 ...
4
votes
3answers
234 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
40 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
40 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
137 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
31 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
70 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
47 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
255 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
496 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
135 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
117 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
66 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
174 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
99 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
109 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
167 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
169 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
202 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
124 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
102 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 ...
0
votes
0answers
51 views

computing centerpoint using linear programming

I was redirected from math.stackoverflow. So I am trying to teach myself discrete geometry and have started with the centerpoint problem. Could someone please help me understand computing ...
4
votes
3answers
284 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
92 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
330 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 ...
28
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
229 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
119 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
599 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 ...
2
votes
0answers
234 views

Accesible Area of Discrete Geometry for Undergraduate Research [closed]

This summer I will have a chance to work on a 16-week summer research project under a professor in convex/discrete geometry. I'm a first-year student with a fairly good background for my age and I've ...
3
votes
0answers
57 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
119 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
95 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 ...