The discrete-geometry tag has no wiki summary.
5
votes
0answers
51 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
29 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 ...
0
votes
0answers
16 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
33 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
59 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
19 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
69 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
79 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
25 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 ...
1
vote
0answers
24 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 ...
0
votes
1answer
76 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
19 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
52 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
44 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) = ...
6
votes
3answers
190 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
123 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 ...
3
votes
2answers
69 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
44 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)$ ...
3
votes
0answers
99 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
56 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
71 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
65 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
98 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
142 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
123 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
95 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 ...
2
votes
0answers
80 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
41 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 ...
3
votes
2answers
121 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
74 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
188 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 ...
25
votes
1answer
831 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
220 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
96 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
306 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
172 views
Accesible Area of Discrete Geometry for Undergraduate Research
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 ...
2
votes
0answers
45 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
113 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
76 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
1answer
136 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 ...
7
votes
4answers
366 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
120 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
180 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 ...
2
votes
2answers
168 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
125 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
65 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
74 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
529 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 calculating all posible distances between any two points
for N=2, line, there is only 1 distance.
for ...
8
votes
1answer
252 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 ...
2
votes
1answer
194 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 ...
