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

learn more… | top users | synonyms

2
votes
1answer
48 views

Bounding the radius of minimum enclosing disk of a finite set

Let $X$ be a finite set of ($n$) points in $\mathbb R^2$ of diameter $1$, i.e. any two points in $X$ have distance at most $1$. We need to prove that $X$ can be included in a disk of radius at most ...
0
votes
0answers
9 views

Shelling of a polytope

During line shelling of a convex polytope in d-dimension, it is easy to see that visible facets are shellable. In the same way non visible facets are also shellable. But while combining these two ...
0
votes
0answers
15 views

Number of point subsets defined by a polygon

If $S$ is set of $n$ points in the plane, then $S$ has $2^n$ different subsets. We say that a subset $T\subseteq S$ is "defined by a polygon" if there is a polygon which has $T$ in its interior and ...
9
votes
1answer
134 views

Infinitely many polygons, no four have a common point

The following question was asked last year at KoMal (May 2015): Do there exist infinitely many (not necessarily convex) 2015-gons in the plane such that every three of them have a common interior ...
1
vote
0answers
33 views

What is the optimal tiling of a regular n-gon in the plane?

I want to tile the plane with equal-sized regular polygons of $n$ sides. Obviously for some $n$, the tiles will be able to tessellate and cover the whole plane (e.g triangles, squares, hexagons) I ...
1
vote
3answers
31 views

Dual set of the unit ball is part of the unit ball.

Define the unit ball centered at the origin as $B=\{x\in\mathbb{R}^d\mid \|x\|\leq 1\}$. Define the dual set of set $X$ as $X^*=\{y\in\mathbb{R}^d\mid\langle x,y \rangle\leq 1\ \forall x\in X\}$. ...
0
votes
0answers
12 views

Reference request: quantifying qualities of a bunch of points using statistics derived from their Delaunay triangulations

I am interested in using Delaunay Triangulations (DTs) to explore the statistics of a cluster of points. Here's an example cluster of points $P$, with its $DT(P)$ (for now, ignore the difference in ...
0
votes
0answers
17 views

Proof of Partition of 6k points into 6 groups of k points using three intersecting lines

Let X ⊂ R^2 be a set of n = 6k points in general position. There exist three concurrent lines separating X into six groups of k points each. So I read Igor Pak's proof of the same-ish thing but with ...
0
votes
1answer
8 views

Efficient volume partition for a set of particles

I am dealing with a set of $N$ dimensionless (point) particles in a box. The box has a certain volume $V$. I need to assign a volume to each particle, whose position within the box changes over time, ...
1
vote
0answers
36 views

Covering unit square

Now, I am reading this topic http://mathoverflow.net/questions/34145/can-we-cover-the-unit-square-by-these-rectangles. And do some research on it. Guys, who had written in topics, have said, that they ...
0
votes
0answers
15 views

Does Elzinga & Hearn algorithm depend on initial points

Elzinga & Hearn is an algorithm which find the smallest enclosing circle of $n$ points in plane. I wonder is it a good idea to initialize the algorithm of Elzinga & Hearn with the two ...
2
votes
1answer
43 views

Bounding solid angle of tetrahedron

Let $K\subset \mathbb R^3$ be a non-degenerate tetrahedron. This tetrahedron has the property that the ratio between diameter and radius of insphere is bounded, $$ d \le \kappa r\ \text{ for some } \ ...
18
votes
2answers
226 views

Largest rectangle not touching any rock in a square field

You want to build a rectangular house with a maximal area. You are offered a square field of area 1, on which you plan to build the house. The problem is, there are $n$ rocks scattered in unknown ...
2
votes
1answer
40 views

When can infinite regular graphs be embedded in the plane?

An infinite $r$-regular graph is a graph with $\infty$ vertices where each vertex touches precisely $r$ edges. We say an $r$-regular graph can be embedded in the $R^2$ Euclidean plane if its set of ...
0
votes
1answer
21 views

formula to count the number edges of a square, cube and tesseract

Given $4$ equidistant points, and the question "how many line segments connect them?", you could rephrase the question to "how many pairs are there in a tuple of 4?" ("pairs" because a line segment is ...
1
vote
1answer
41 views

Polar set of convex cone

I am stuck with the following question: Let $K = \{x\in \mathbb{R^n}: x_1 \geq x_2 \geq ... \geq x_n \geq 0\}$. Determin $K^{*}$, which is supposed to be the polar set of $K$. I know that $K$ is a ...
0
votes
0answers
34 views

Polar set of convex cones Proof

I have to show the following: Let $K_{1}, K_{2} \subseteq \mathbb{R}^{n}$ be convex cones with $K_{1} \cap K_{2} = \begin{Bmatrix} 0 \end{Bmatrix}$ and $intK_{i} \neq \varnothing , i=1,2$. Show that ...
3
votes
0answers
40 views

Elementary proof of Jordan curve theorem for polygons

Courant described the outline of an elementary proof of the Jordan curve theorem for polygons using the order of points: The order of a point $p_0$ is defined by the net number of complete ...
0
votes
0answers
23 views

Simplicial polytope Dehn-Sommerville Equations

Let's suppose we have a polytope P with $dim(P)=d$ and the h vector $ h(P,x)=\sum\limits_{i = 0}^{n} h_ix^{d-i}$ i have to prove that if $h_{k}=h_{d-k}$(simplicial polytope) then $xh(P,x)=h(P,1/x)$ ...
0
votes
1answer
48 views

Show that T(n)=4×T(n−1)−T(n−2)

T(n) is the number of spanning trees for a n-ladder. Show that $ T(n)=4×T(n−1)−T(n−2) $ As a proof, I don't really know how to solve this. Any assistance would be appreciated. I tried to first ...
0
votes
1answer
112 views

Distance 2 neighbors in a directed graph

Consider a directed graph G in which there is exactly one edge between any two distinct vertices in G. Prove that there is a vertex in G that is in the distance-2 neighborhood of every other vertex in ...
0
votes
0answers
22 views

Discrete Geometry

I have a homework assignment, but I am currently a blockade and have no clue how to do this: Determine the smallest number $\mu(d)$ such that every set of $\mu(d)$ points X = {x1, x2, ..., xμ(d)} in ...
0
votes
0answers
25 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 ...
1
vote
0answers
33 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
18 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
79 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
9 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 ...
2
votes
2answers
57 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
42 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
81 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
53 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
39 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
16 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 ...
2
votes
2answers
74 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
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
68 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
43 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 ...
4
votes
1answer
105 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
48 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
47 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
135 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
25 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
23 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 ...
1
vote
1answer
27 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
51 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
25 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
22 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
150 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
0answers
28 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
15 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 ...