Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-geometry]

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

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

Discrete geometry has large overlap with convex geometry and computational geometry, and is closely related to subjects such as finite geometry, combinatorial optimization, digital geometry, discrete differential geometry, geometric graph theory, toric geometry, and combinatorial topology.

733 questions
2
votes
0 answers

volumetric discrete Laplacian

The graph Laplacian is a common way to get a discretized version of the Laplacian differential operator on graphs and I recently learned about another discrete Laplacian for triangle meshes, often called cotangent Laplacian. Is there also an…
yewang
  • 249
  • 1
  • 6
2
votes
0 answers

a convex polygon $P$ can be partitioned into parallelograms

Prove that a convex polygon $P$ can be partitioned into parallelograms if and only if it $P$ is centrally symmetric. I can just verify the one side as follows: Let $P$ be a polygon that can be dissected into parallelograms. Subdivide to assume that…
MathFun
  • 438
2
votes
0 answers

Maybe application of Helly theorem

Let $X$ be a compact subset of $R^n$. Prove that if any $≤ n + 1$ points of $X$ can be covered by a unit ball not containing the origin then the whole $X$ can be covered by a unit ball not containing the origin. Note: If we remove the condition that…
123...
  • 959
2
votes
0 answers

Colorful Tverberg’s theorem for special case

(Colorful Tverberg’s theorem by Barany and Larman). Let $n$ red, $n$ green, and $n$ blue points be given in the plane. then it is possible to partitions the points into n triples, each consisting of different colors, so that the $n$ corresponding…
123...
  • 959
2
votes
0 answers

Finite family of red and blue lines

Let a finite family of red and blue lines in the planes be given. Assume no two given lines are parallel and through any intersection point of two lines of the same color, there passes a line of the other color. Prove that all the given lines, in…
123...
  • 959
2
votes
1 answer

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 that line would toggle their color. Prove there is…
n0vakovic
  • 909
1
vote
1 answer

dual set of the dual set

Let $X\subseteq\mathbb{R}^d$ and let $X^*$ be it's dual set i.e. $X^*=\{y\in\mathbb{R}^d| \leq 1$ for every $x\in X\}$. How to prove that $(X^*)^*=\overline{conv(X\cup\{0\})}$? I know that $(X^*)^*$ is convex, closed and that it contains origin…
Pape
  • 43
1
vote
1 answer

Wrong formulation of Helly's theorem

In Lectures on Discrete Geometry, Matousek writes (p.11) (excerpt here): It is very tempting and quite usual to formulate Helly's theorem as follows: "If every $d+1$ among $n$ convex sets in $\mathbb{R}^d$ intersect, then all the sets …
Greg82
  • 261
1
vote
1 answer

$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 the (euclidean) plane. My current worst case…
stefan
  • 1,030
1
vote
0 answers

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 vector at $p$ and $k_H(p)$ the mean curvature. Then…
M.B.
  • 3,276
1
vote
1 answer

The convex hull of a function.

I'm doing this exercise which gives the following definition of the convex hull of a function. Doesn't this definition make $g(x) = f(x)$?
ensbana
  • 2,277
1
vote
1 answer

Packing points in a ball of radius 1, where every point is $\sqrt{2}$ apart

Problem: Let $c_1, \dots , c_n$ be points of $\mathbb{R}^d$ in a ball of radius $1$ so that the distance between any two of them is strictly greater than $\sqrt{2}$. Show that $n \le d+1$. I need this result for a different problem, but my…
Wesley
  • 1,567
1
vote
0 answers

A problem similar to colorful caratheodory theorem

Suppose that $T$ and $S$ are two $(d + 1)$-element sets in $\mathbb{R}^d$ such that $o\in conv(x : x\in T)$ and $o\in conv(x : x\in S)$. Prove that there is a sequence of $(d + 1)$-element sets $S_0 = T, S1, . . . , S_{d+1} = S$ such that…
MathFun
  • 438
1
vote
1 answer

I made a map that violated four color map theorem, what am I doing wrong?

Hi, so I made this map. I was wondering what I did wrong.
Srijan agrawal
  • 21
1
vote
0 answers

Finite set of grid points inside of grid verticed $n$-gones

Trying to prove: There is finite set of triangles with vertices on a grid enclosing any finite set of grid points. While there are infinite set of $n$-gones enclosing the same set for $n\ge4$. Some samples follow: for 1 point: $n$-gons on grid with…
Gevorg Hmayakyan
  • 1,698
1
2
3