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

learn more… | top users | synonyms

0
votes
0answers
28 views

Proof that dimension of set is n

I have a Discrete Geometry question and I would really appreciate if someone could help me out with this. I have a set $K\subset \mathbb{R}^n$ s.t. $int(B_{n}) \subseteq K \subseteq B_{n}$ where $int(...
2
votes
0answers
46 views

Probabilistic proof for sphere covering upper bound

I would like to show an upper bound for the number of $d$-dimensional spheres needed to cover some closed, bounded subset of $\mathbb{R}^d$, like a cube or another sphere. I could do this by placing ...
1
vote
1answer
22 views

How to find a line that stabs the maximum possible number of segments?

Suppose we are given $N$ arbitrary different angle segments in the plane that are disjoint, and we want to find a line that stabs the maximal number of segments. How to do this? I thought about quad ...
3
votes
1answer
87 views

Minimum number of internal diagonals of a simple $n$-gon

What is the least number of internal diagonals a simple $n$–gon may have? (For a fixed $n$) I know that any simple polygon has at least one internal diagonal. The main problem is with the concave ...
0
votes
0answers
11 views

Explanation of defintion of packing number

$X$ is a ground set, and $\mathcal F$ is a system of sets on $X$. Packing/matching number of $\mathcal F$ is defined as: $\nu(\mathcal F) = \sup\{|\mathcal M|: \mathcal M \subseteq \mathcal F, M_1 \...
3
votes
2answers
77 views

non-trivial non-repetitive aperiodic tiling of the plane

Which is the less trivial example of non-repetitive aperiodic tiling of the plane you know? I cannot come up with a famous non-repetitive tiling. Are there any? A tiling is repetitive if for every ...
0
votes
1answer
56 views

Proof of Jordan Curve Theorem for Polygons

So I'm trying to prove the Jordan curve theorem for polygons, but I'm not sure how to show that a line segment that does not intersect the boundary has all points of the same parity. I'm also not ...
2
votes
2answers
120 views

Polygons with a Unique Triangulation

For each n > 3, find a polygon with n vertices that has a unique triangulation. I want to say that you can somehow build these polygons by continuously adding triangles somehow, but I'm not sure.
0
votes
1answer
55 views

Equivalent definitons of Centerpoint

In Jiri Matousek's book - "Lectures on Discrete Geometry", he defines centerpoint as: 1.4.1 Definition (Centerpoint). Let $X$ be an $n$-point set in $\mathbb R^d$. A point $x \in \mathbb R^d$ is ...
0
votes
0answers
60 views

Relationship between Laplacian and Taylor expansion for 2nd derivative

I am working on converting a solution to a certain PDE from working on a regular 2D grid to work on a 3D triangular mesh. In the 2D scenario the 1st and 2nd derivatives are, of course, approximated ...
1
vote
0answers
21 views

What is the expected number of edge flips to get from a random triangulation to this special min-max angle triangulation in 2-d?

This comes from a problem my coworker and I are working on, and I'm not sure whether to post it here or MathOverflow or CrossValidated or what. Please let me know if I should migrate the question. We ...
0
votes
1answer
19 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 ...
8
votes
2answers
74 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 ...
1
vote
0answers
50 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 ...
16
votes
1answer
171 views

Curtains and groups

This picture is a copy of the pattern on my curtains. The points of a hexagonal lattice are each coloured with one of four possible colours. It has translational symmetry in two directions: a ...
4
votes
1answer
116 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 ...
0
votes
1answer
55 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 ...
1
vote
1answer
52 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
159 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
27 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?
1
vote
1answer
32 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
54 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 ...
2
votes
0answers
29 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
23 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 ...
5
votes
2answers
172 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 } \...
0
votes
1answer
152 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 ...
6
votes
2answers
65 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 ...
3
votes
3answers
299 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
30 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 ...
35
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 the ...
1
vote
1answer
113 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 ...
6
votes
0answers
60 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 ...
1
vote
1answer
191 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 ...
1
vote
0answers
74 views

How many distinct area histograms I can get by partitioning a M x N rectangle?

Given a $M \times 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 ...
0
votes
0answers
49 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
38 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 \cup_{...
1
vote
0answers
83 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
1answer
33 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 ...
1
vote
1answer
102 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
47 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 ...
4
votes
2answers
156 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 4-...
1
vote
1answer
42 views

Prove that a planar bipartite graph on n nodes has at most 2n−4 edges.

I know that we have to use Euler's formula ( v−e+f=2) but I don't understand how f = e/2.
3
votes
2answers
258 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 ...
2
votes
1answer
75 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
272 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 $(Y,\...
0
votes
3answers
46 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 ...
10
votes
2answers
190 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 ...
0
votes
2answers
42 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
1
vote
1answer
49 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 ...