Tagged Questions

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

learn more… | top users | synonyms

3
votes
0answers
58 views

Polytopes-Discrete Geometry

Can someone help me solve the following question please? Let v be a vertex of a d-polytope P such that $ 0 \in intP $ . Prove that $ P^{*} \cap \{ y \in \mathbb{R}^d \mid\left < y, ...
1
vote
1answer
119 views

Restricted Cube Packing

I want to pack n cubes in 3-space under the following 3 restrictions: 1) At each vertex only 2 cubes may touch 2) No two cubes may share an edge 3) No two cubes share any subface 2,3 just mean ...
1
vote
1answer
95 views

Maximum number of points with a fixed minimum distance in a $d$-dimensional ball

Let $c \leq r$ be real numbers greater than $0$, $d \in \mathbb{N}$ and $B_r(0) = \lbrace x \in \mathbb{R}^d \mid \Vert x \Vert \leq r \rbrace$, the ball with radius $r$ at point $0$ ($\Vert \cdot ...
3
votes
2answers
170 views

crossing number question

Prove that there exists constant k such that, for all $5v < e$ there is a subgraph of the complete graph of $v$ vertics with crossing number less or equal than $ k e^3/v^2$. Any hints for a way to ...
9
votes
4answers
921 views

Every polygon has an interior diagonal

How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon. In ...
4
votes
3answers
127 views

What is the name of this property?

If there are 3 intervals, such that any 2 of them intersect, then all 3 of them intersect. For any 4 disks, if any 3 of them have a non empty intersection, then all 4 of them have a common ...
5
votes
3answers
229 views

Number of point subsets that can be covered by a disk

Given $n$ distinct points in the (real) plane, how many distinct non-empty subsets of these points can be covered by some (closed) disk? I conjecture that if no three points are collinear and no four ...
3
votes
2answers
238 views

Find center of circle of radius $r$ that overlaps exactly $\lfloor \pi r^2 \rceil$ points of the integer grid

Can a circle of a given radius $r$ always be placed (in $\mathbb{R}^2$) such that the number of points with integer coordinates inside the circle is equal to the nearest integer of the circle's area? ...
3
votes
1answer
158 views

Intersection of Disks

If I have a disk $d$ where each point of the disk is contained in at least $k$ other disks, then at least how many other disks does $d$ intersect? Given, that all the disks (including $d$) have the ...
0
votes
1answer
76 views

$n$ points in disk, determine number of close distances

If I have a disk of radius $r$, and $n$ points inside this disk, I'm interested in the minimum number of distances $\leq r$ between the points, when the minimum is taken over all $n$ point sets in ...
2
votes
1answer
82 views

How to calculate number of lumps of a 1D discrete point distribution?

I would like to calculate the number of lumps of a given set of points. Defining "number of lumps" as "the number of groups with points at distance 1" Supose we have a discrete 1D space in this ...
1
vote
2answers
1k views

Mean distance between N equidistributed points in a circle

I would like to calculate the mean distance depending on circle shape points, This is a mean calculating all posible distances between any two points for N=2, line, there is only 1 distance. for ...
8
votes
1answer
343 views

“Center-of-Mass” of lattice polygons (generalization of Pick's theorem)

Call a polygon with integer coordinates (in the Euclidean plane) a 'lattice polygon'. Pick's Theorem allows you to efficiently compute the number of lattice points inside this polygon given just its ...
3
votes
1answer
340 views

Which internal angles can a lattice polygon have?

I am wondering if for a lattice polygon an internal angle can take any value? If no which ones not and why? I guess there will be some restrictions due to the discrete nature of the grid but I am ...
2
votes
2answers
194 views

Cover n points with n disjoint unit disks

This is a problem I saw on Peter Winkler's column on communication of the ACM(might be under a pay wall). It is open. What is the largest $n$, such that you can always cover a given set of $n$ points ...
1
vote
0answers
85 views

Lipschitz constant of the Laplace-Beltrami operator

I'm reading a paper on discrete differential geometry: Meyer et.al. They define the Laplace-Beltrami operator at a point $P$ by $$\vec{K}(p) = 2k_H(P)\vec{n(P)}$$ where $\vec{n}(p)$ is the normal ...
1
vote
1answer
81 views

Cutting a d-simplex

Why is it possible to get any possible subset of nodes of a d+1 simplex in IR^d using halfspaces?
3
votes
1answer
494 views

Applications of Morse theory

Background The use of tools from algebraic topology to study simplicial complexes coming from point cloud data has been thoroughly discussed in the papers of Carlsson, Zomorodian, Ghrist, ...
1
vote
0answers
102 views

Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel. It is clear that by extending the edges of each simple $n$-gon in ...
1
vote
1answer
265 views

How close are star-convex sets to convex sets?

What interesting properties of convex sets are retained by star-convex sets?
11
votes
1answer
245 views

Reconstructing a Monthly problem: tree growth on the 2D integer lattice

I'm trying to reconstruct a problem I saw in the Monthly, years ago. Perhaps it'll look familiar to someone. In the integer lattice in the plane, we grow a tree in the following natural way: ...
55
votes
4answers
6k 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 number? I'm ...
10
votes
1answer
529 views

Results related to The Happy Ending Problem

Im giving a small talk for a combinatorics class on the Erdos-Szekeres conjecture regarding the happy ending problem (the paper is focused on recent work regarding the conjecture). I always find that ...
10
votes
1answer
434 views

A multi-dimensional Frobenius problem

Inspired by this question. Let $A$ be a subset of ${\mathbb Z}^d$ that generates the whole additive group ${\mathbb Z}^d$, and let $S$ be the additive semigroup generated by $A$. Prove that there ...
2
votes
5answers
198 views

Existence of lines not containing given points in general position

I remember seeing something like the following problem in the past and would like to know if it has a solution (or if I can find a source for it). Problem Given a finite set of points in the plane in ...
3
votes
2answers
376 views

Voronoi decomposition implementation in four dimensions?

I'm a software engineer and have been asked to research a Voronoi implementation in four dimensions. I'm not asking for "teh codez" but am interested in approachable tutorials on Voronoi decomposition ...
3
votes
1answer
126 views

Lower bound for a set of distances between pairs of points in a plane

There are $N>1$ points in a plane. Consider the set of all distances between pairs of the points. Let $n$ be the number of elements of this set. We know that $$n \leq {N \choose 2}.$$ What is the ...
1
vote
1answer
263 views

Black and White points on a grid

Some points on (integer, rectangular) grid in a plane are colored white, some black and some are not colored. In each step, one vertical or horizontal line can be selected, and all colored points on ...
1
vote
2answers
678 views

Distinct Hamiltonian cycles of the icosahedron and dodecahedron

I am seeking a listing of the distinct Hamiltonian cycles following the edges of the icosahedron and the dodecahedron. By distinct I mean they are not congruent by some symmetry of the icosahedron or ...
17
votes
5answers
1k views

Pick's Theorem on a triangular (or hex) grid

Pick's theorem says that given a square grid (that is, all points in the plane with integer coordinates) and a polygon without holes and non selt-intersecting whose vertices are grid points, its area ...
4
votes
3answers
330 views

Euclidean Tilings that are Uniform but not Vertex-Transitive

Basic definitions: a tiling of d-dimensional Euclidean space is a decomposition of that space into polyhedra such that there is no overlap between their interiors, and every point in the space is ...