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
1
vote
1 answer

$n$-gons on grid with $1$ internal grid point

Investigating the triangle with $1$ internal point: There are at least $5$ triangles: EDITED: According to comment adding the $3$-rd case: Is it known how many triangles and $n$-gons in general exist with $1$ internal point.
Gevorg Hmayakyan
  • 1,698
1
vote
0 answers

Convex set and its mirror Image

Let $X$ be a convex compact subset of $\mathbb{R}^d$. Prove that there exist a vector $u$ such that $-\frac{1}{d}X+u\subseteq X$. My idea is that: For each $x\in X$, put $A_x=\{u : -\frac{1}{d}x+ u\in X\}$. It is very easy to see that all of $A_x$…
MathFun
  • 438
1
vote
1 answer

The h vector of a pyramid

I have an exercise that asks me to find the h vector of a pyramid which has a d-polytope as its base, and I have no idea what to do, so I would appreciate any help, solution or intuitive approach Thank you in advance
Greg
  • 21
0
votes
1 answer

2D discrete Jordan curve theorem: what about the "boundary points"?

Let us say we have a polygon $P$ in $\mathbb{R}^2$, with edges in the set $E$ (the boundary), and vertices in the set $V$. Let us say we have a point $Q$ such that $Q$ lies on one of the edges in $E$. Let the direction of a vector not parallel to…
bzm3r
  • 2,632
0
votes
0 answers

If a line intersects three segments in the plane, then must there be a line through endpoints of two of the segments while intersecting the third?

Assume we are given 3 segments in the plane so that there exists a line intersecting them. Regardless of their disjointness, can we always say that there is a line that is tangent to two of them while intersecting the third one? (Here, a line is…
user883624
0
votes
1 answer

Closure of a set is contained in the half space

If $X\subset\mathbb{R}^{d}$ lies in the closed half-space $\mathbb{h}^{+}$, then the closure $\text{cl} X$ of $X$ also lies in $\mathbb{h}^{+}$. I understand the question but I don't have any idea how to prove this. Any hints/ help would be great.…
SpeedForce
  • 501
0
votes
1 answer

Dual set of the unit ball with radius r

Define the unit ball centered at the origin with radius r as $B(0,r)=\{x \in \mathbb{R}^d:||x||\leq 1\}$ Define the dual set of a set X as $ X^*=\{y \in \mathbb{R}^d: x^Ty \leq 1,\; \forall x \in X \} $ I'm trying to prove that the dual set of…
SSG19
  • 53
0
votes
1 answer

Any $d+1$ affinely independent points can be shattered by the half spaces in $\mathbb R^d$

I am studying the VC-dimension of half spaces. There is a theorem in my book stating that, if $\mathcal H$ is the family of half spaces in $\mathbb R^d$, then VC-$dim(\mathcal H)=d+1.$ And the proof said that any $d+1$ affinely independent points…
mdryizk
  • 57
0
votes
1 answer

Examples of locally finite set whose convex hull is the whole $\mathbb{R}^n$.

In our exercise a locally finite set A is a set such that $A \cap B(r)$ is a finite set for all $r \geq 0$, where $B(r)$ is the ball centered at $0$ and has radius $r$. Shouldn't conv($A$) then be bounded?
ensbana
  • 2,277
0
votes
0 answers

Maximum size of an "open convex polygon" made by intersection of lines?

Suppose we have $n$ lines in the plane. What is the maximum size of an "open convex polygon" that we can get from the intersection of lines? For example, in the following picture, we can see an "open" triangle coming from the intersection of three…
Ken
  • 780
0
votes
0 answers

Points in general position form convex polygon

Find an upper bound for n points if these n points in general position form empty convex pentagon I don't understand the meaning
S Mukherjee
  • 107
0
votes
0 answers

axis parallel rectangles

Assume $\mathcal{F}$ such a family of axises-parallel rectangles, any two of them intersects by a horizontal or vertical line. Prove there exist a pair of line $(v, h)$ vertical and horizontal such that any $R\in\mathcal{F}$ intersects any of…
123...
  • 959
0
votes
1 answer

Intersection segments

Assume $\mathcal{F}$ is a finite family of closed interval and $k\geq 2$, such that among any $k+1$ segments $I_0, I_1, \cdots, I_k\in F$ some two of them intersects. Prove there exist $k$-point set $X$ such that $$\forall I\in\mathcal{F}; I\cap…
123...
  • 959
0
votes
1 answer

Helly's theorem

Given the system of closed arcs from the same circle, with length smaller than half circumference of that circle. If every three arc from that system have non-empty intersection, then intersection of all arcs is non-empty. How can I prove this? How…
user354021
-2
votes
1 answer

Polygon with integer vertices

Prove that a convex 1000000-gon with integer vertices (both coordinates integer) has a side of length at least 550.
MathFun
  • 438
1 2
3