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
47 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$ ...
5
votes
1answer
78 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 ...
66
votes
5answers
9k views

Why is a circle in a plane surrounded by 6 other circles?

When you draw a circle in a plane you can perfectly surround it with 6 other circles of the same radius. This works for any radius. What's the significance of 6? Why not some other numbers? I'm ...
6
votes
1answer
462 views

Surface integral for a scalar function defined on a discrete surface

Imagine a polyhedral, discrete surface embedded in $\mathbb{R}^3$. Its faces are all triangles. For each vertex, one can compute the discrete mean and Gaussian curvatures and evaluate the sum of ...
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 ...
7
votes
4answers
157 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 ...
1
vote
0answers
34 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 ...
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
46 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.
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 ...
1
vote
1answer
249 views

Determining if a set of hexagons on a grid can tile the plane

Suppose I have a regular grid of identical hexagons that tile the plane, that is a hexagonal lattice. How can I determine if a connected subset of these hexagons (i.e. a poly-hex) can tile the plane ...
1
vote
0answers
73 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 ...
16
votes
1answer
170 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 ...
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 ...
4
votes
1answer
445 views

Poisson point process (PPP) and Voronoi cells

Say we have a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. In one realization of the PPP we get the points $\phi=\{x_1,x_2,...,x_i,...\}$. Now we generate the Voronoi cells ...
2
votes
1answer
46 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
29 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 ...
0
votes
1answer
31 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
2answers
94 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 ...
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
45 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
736 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?
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 ...
3
votes
1answer
84 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 ...
2
votes
0answers
47 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 \...
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
2answers
118 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.
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 ...
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'...
31
votes
1answer
2k 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 $C(p)...
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, ...
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 ...
29
votes
6answers
969 views

Prove Existence of a Circle

There are two circles with radius $1$, $c_{A}$ and ${c}_{B}$. They intersect at two points $U$ and $V$. $A$ and $B$ are two regular $n$-gons such that $n > 3$, which are inscribed into $c_{A}$ and ...
6
votes
2answers
229 views

Squaring the plane, with consecutive integer squares. And a related arrangement

Q1. I was fiddling around with squaring-the-square type algebraic maths, and came up with a family of arrangements of $n^2$ squares, with sides $1, 2, 3\ldots n^2$ ($n$ odd). Which seems like it would ...
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 ...