Tagged Questions

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

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 ...
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 ...
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: ...
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 ...
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 ...
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.
12 views

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$, ...
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|$. ...
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?
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 ...
6 views

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 \... 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-... 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/... 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,... 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\... 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 ... 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 ... 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 ... 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'... 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 ... 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 ... 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, ... 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 ... 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 ... 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 } \ \... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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)$... 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 ... 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 ... 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(...
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 ...
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 ...