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

learn more… | top users | synonyms

5
votes
1answer
79 views

Upper bound on the minimum distance between $N$ points chosen inside the unit circle?

I guess this is a well-known problem but I'm not sure where to find it on the web. $N \ge 2$ points are chosen in the interior or the boundary of the unit circle. What is the best upper bound on the ...
2
votes
0answers
31 views

Convergence of Discretized Geodesics?

Let $M$ be a Riemmanian manifold, $p\in M$ and $V\in T_p(M)$. Suppose $f^{-1}:U_p \mapsto \mathbb{R}^D$ is a diffeomorphism of a neighborhood of p to an open subset of $\mathbb{R}$ and define the ...
1
vote
0answers
14 views

Geometric median (or Fertmat-Webber problem), including continuous case

For a finite set $X\subset \mathbb R^n$ the geometric median is defined as the point in $\mathbb R^n$ for which the sum of distances to all points of $X$ attains its minimum. Here is a wiki article: ...
0
votes
1answer
18 views

Projective Geometry: Combinatorially, but not projectively equivalent polytopes

I have a hard time understanding Projective Geometry. My task is to Find two polytopes, that are combinatorially, but not projectively equivalent. What combinatorially equivalent means is ...
0
votes
0answers
13 views

Gaussian blur over (or random walk in) a surface mesh

Let $V$ be the set of mesh vertices, connected by edges $E$, forming a mesh that represents a surface embedded in $\mathbb{R}^3$. On this mesh a function $f:V\rightarrow\mathbb{R}$ is defined. For ...
3
votes
0answers
27 views

Textbook Recommentation: Discrete Differential Geometry

are there any good books that provide a good introduction to Discrete Differential Geometry to beginners? Thanks a lot.
0
votes
0answers
12 views

Dual of cartesian product of duals of polytopes

I am working on the following problem. Let $P\subseteq \mathbb{R}^d, Q\subseteq \mathbb{R}^e$ be full-dimensional polytopes, both with the origin in the interior. Describe $(P^{\circ }\times Q^...
3
votes
0answers
47 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
5
votes
2answers
61 views

21 points on circumference of a circle must have at least 100 pairs separated by 120+ degrees.

Prove that at least 100 of the arcs determined by the pairs of these points subtend an angle not exceeding 120 degrees at the center. How do I prove this? Induction? Help please. Thanks.
5
votes
1answer
48 views

Plane tesselation, using stairs $n\times n$, is it possible?

The other day I was constructing new mathematical problems for my pupils and thought of something like this: Given the infinite sequence of "stairs" $n\times n$, constructed from $1\times1$ ...
0
votes
0answers
18 views

Points on the moment curve form the vertices of the corresponding cyclic polytope

Working through Matousek and I am stuck on exercise 5.4/1a Show that if V is a finite subset of the moment curve, then all the points of V are extreme in conv(V); that is, they are vertices of the ...
0
votes
0answers
8 views

Sufficiently many points in $\mathbb{R}^d$ must contain $m$ points forming the vertices of a convex polytope?

Let us say that a set of points in $\mathbb{R}^d$ is minimal if it forms exactly the set of vertices of a convex polytope. Equivalently, no proper subset of the points has the same convex hull; no ...
0
votes
0answers
25 views

minimal number of sets of binary vectors

I have a set of binary vectors that I would like to group into a minimal number of sets. A set can be formed when it contains all combinations of elements that vary within that set. Example: for {...
3
votes
0answers
33 views

Asymptotic bounds on the number of faces needed to construct a polyhedron of a certain genus

Let a polyhedron be a solid in three dimensions with flat polygonal faces, straight edges and sharp corners or vertices, where moreover we require that every edge touches exactly two faces, every ...
2
votes
1answer
47 views

Set of diameter < 1 is contained in a disc of radius $\frac{1}{\sqrt 3}$

Exercise from Matousek Lectures in Discrete Geometry Prove that each set $X \subset \mathbb{R}^2$ of diameter at most 1 (i.e., any two points have distance at most 1) is contained in some disc of ...
3
votes
1answer
30 views

Tetrahedra require octahedra; 5-cells require…?

It's well known that equilateral triangles tessellate $\Bbb R^2$ but regular tetrahedra do not tessellate $\Bbb R^3$. However, in three dimensions, we can make a a tessellation if we are permitted to ...
3
votes
2answers
96 views

how to divide a hexagon into regular polygons

I want to cut a hexagon paper into regions of equal areas (more precisely either into squares of side c or into regular hexagons of side c). In both cases some of the papers will be wasted. Is it ...
0
votes
1answer
32 views

Correctness of the sweep line algorithm for line segment intersection in the plane

Suppose we are given a finite set $S$ of line segments in the plane and the intersection between two segments is empty or a single point in the interior of both segments at most two segments ...
3
votes
1answer
52 views

Set of diameter $\le 1$ contained in set of constant width $1$

I'm reading the paper 'Minimal universal covers in $E^n$ by H G Eggleston and they state that every set $A\subseteq{\bf R}^2$ of diameter at most $1$ (the diameter of $A$ is defined as $\sup_{x,y\in A}...
1
vote
0answers
15 views

Lebesgue covering problem's demand for convexivity

Is there a specific reason why in the Lebesgue (universal) covering problem only convex sets are admitted as universal coverings? I see that for any set $X\subseteq{\bf R}^2$ of diameter $\le\alpha$, ...
1
vote
1answer
46 views

Given two sets of points in the plane, there exists a point with equal sum of distances to the points in each set

Let ${A_1, ..., A_n}$ and ${B_1, ..., B_n}$ be two given sets of points in a plane with different centroids. Prove that there exists a point $P$ in the plane such that $\sum |PA_i| = \sum |PB_i|$. ...
19
votes
6answers
737 views

Circle enclosing all but one of $n$ points

It looks like a simple question but it turns out rather difficult to me. Here is the question: Given $n$ points on the plane, can we always draw a circle that includes exactly $n-1$ of them?
1
vote
0answers
35 views

On partitioning a finite set of points in the plane by drawing a line

Number of ways to separate $n$ points in the plane The linked answer was to this question: Suppose you have $n$ points in the plane, no three of which are colinear. How do you show that the number ...
0
votes
0answers
6 views

Arrangement of Convex Discs in the plane is independent of the choice of origin?

This is the Problem 3.1 in 'Combinatorial Geometry' by J. Pach, and P. Agarwal. Problem: Prove that if C is any arrangement of convex discs in the plane, then $\bar{d}$$(C,\mathbb{R}^2)$ and $\...
-1
votes
0answers
34 views

What is the 4D axis of rotation for Necker cube inversion? [closed]

See the figure on top of page 47 of Rudy Rucker's book. https://books.google.com/books?id=Vgk7BAAAQBAJ&pg=PA49&lpg=PA49&dq=neck+a+cube+rucker&source=bl&ots=B-roCAijR0&sig=-Z-...
2
votes
1answer
57 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 $1/...
0
votes
0answers
15 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 part,...
0
votes
0answers
19 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 $S\...
11
votes
1answer
156 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 ...
7
votes
4answers
161 views

How many acute triangles can be formed by 100 points in a plane?

Given 100 points in the plane, no three of which are on the same line, consider all triangles that have all their vertices chosen from the 100 given points. Prove that at most 70% of those triangles ...
2
votes
0answers
50 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
38 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\}$. I'...
0
votes
0answers
16 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
20 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
41 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
20 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 points ...
2
votes
1answer
48 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
250 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
52 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
39 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
49 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
37 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
50 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 ...
1
vote
0answers
41 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
50 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
139 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
27 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
44 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 ...