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

learn more… | top users | synonyms

0
votes
1answer
17 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
11 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
21 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
11 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 ...
0
votes
0answers
19 views

Rotate circle about line if a point on circle is on the line

I'm working with unit-distance graphs in $\mathbb{R}^3$, so all points are in $\mathbb{R}^3$ and points $x$ and $y$ are adjacent (notation: $x \sim y$) if and only if $|x-y|=1$ (where $|x-y|$ denotes ...
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.
5
votes
0answers
36 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
16 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
44 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
25 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
82 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
28 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
50 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 ...
1
vote
0answers
14 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
44 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
730 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
31 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. ...
2
votes
1answer
55 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
14 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
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 ...
11
votes
1answer
154 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
149 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
47 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
37 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
15 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
40 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
19 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
44 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
37 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
47 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
48 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
38 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
133 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
26 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 ...
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 ...
3
votes
1answer
81 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 ...