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

learn more… | top users | synonyms

1
vote
1answer
11 views

Is optimal bound for Alcuin's triangular city problem known?

Alcuin's triangular city problem is Problem 28 from Propositiones ad Acuendos Juvenes. There is a triangular city which has one side of 100 feet, another side of 100 feet, and a third of 90 ...
0
votes
0answers
21 views

What does this statement mean exactly?

I would like some clarification about the following from Fejes Toth's paper "A stability criterion to the moment theorem" The setup is: For each positive integer $n$, let $r(H_n)$ and $R(H_n)$ ...
2
votes
1answer
39 views

triangulation of the cube of whose vertices are in the set $\lbrace (\pm 1 , \pm 1 , \dots , \pm 1)\rbrace$

Take the cube centered at the origin whose vertices are $\lbrace (1 ,1 , 1) , (-1 ,1 , 1) , (1 ,-1 , 1) , (1 ,1 , -1) , (1 ,-1 , -1) , (-1 ,1 , -1) , (-1 ,-1 , 1) , (-1 ,-1 , -1) \rbrace$. We can ...
2
votes
0answers
22 views

Intersection of a polyhedron and a ball

I'm reading this paper http://www.math.hawaii.edu/~erik/papers/cat0-A.pdf and it looks like I don't get one point. It's the remarks under definition 2.2., mostly the sentence: ,,Imagine a vertex $ x ...
0
votes
0answers
12 views

Finitely many hyperplanes separating $ x,y $ in a CAT(0) cube complex

I'm having a great difficulty understanding a proof of a lemma from this paper: http://www.math.hawaii.edu/~erik/papers/cat0-A.pdf It's lemma 1.12. To make it shorter for anyone who'd like to take a ...
5
votes
2answers
116 views

Convex polyhedron and its Gauß-curvature

I am trying to prove: A convex polyhedron has positive Gauß-Curvature at every vertex. What we know: Gauß-Curvature at every vertex is given by $K(p) = 2\pi - \sum\limits_{\text{angle } ...
0
votes
0answers
14 views

Plane division by lines

I need help with solving a combinatorial problems. In the plane is m parallel lines. We choose in the same plane n lines, of them no 2 are parallel and each of which are intersecting with given m ...
0
votes
0answers
12 views

Good bounds on non-zero integers assigned to regions of a line arrangement so that sum of integers on each side of each line is 0

Suppose there is a line arrangement in the plane of $n \geq 2$ lines (collection of lines that defines all disjoint positive area subregions with boundaries given by some of the lines), and there are ...
1
vote
0answers
25 views

Center of mass of voronoi cells of 3d lattice

Let $v_1,v_2,v_3$ be linearly independent vectors in $\mathbb{R}^3$, and let $A$ be a matrix whose columns are $v_1,v_2,v_3$. i.e. $A = [v_1,v_2,v_3]$ Then, define a lattice $\Lambda$ as $\Lambda = ...
0
votes
1answer
42 views

upper bound and a lower bound on the number of points that are uniformly distributed on a surface

Can I calculate an upper bound and a lower bound (or max or min) on the number of points that are uniformly distributed on a surface, knowing the area of the surface ? More precisely, I have a sector ...
0
votes
0answers
36 views

About Katz centrality

I am studying Graph Theory and Network Analysis, I have this measurement formula which called Katz centrality: My question is: why $A^k$ will grow [infinitely] in $k$ for most cases. As I think ...
6
votes
2answers
45 views

Which planar angles on an integer lattice are possible?

As shown in this question, you can construct an angle $A$ on 3 integer points on a plane only if $\tan A$ is rational. A natural generalization is to ask which values can planar angles based on 3 ...
3
votes
3answers
273 views

Cover a cicular hole with planks

A friend of mine asked me the following question. Whats the minimum number of rectangular planks of unit width (and infinite length) needed to cover a circular hole with diameter $n$? ...
0
votes
0answers
23 views

Homomorphisms between countable spaces and Euclidean spaces?

Is there some place to start reading about homomorphisms between countable (discrete) spaces and Euclidean spaces or $l_2$? I know it is a rather general question, but I am not sure what I am looking ...
0
votes
0answers
27 views

Intersection of two convex lattices polygons

A convex lattice polygon is a polygon whose vertices are points on the integer lattice. Let P and Q two convex lattice polygons with n ,(resp. m) vertices. Let R be the convex lattice polygon ...
33
votes
2answers
2k views

Why can't three unit regular triangles cover a unit square?

A square with edge length $1$ has area $1$. An equilateral triangle with edge length $1$ has area $\sqrt{3}/4 \approx 0.433$. So three such triangles have area $\approx 1.3$, but it requires four ...
0
votes
1answer
30 views

What does R^d in last lines refer to

The image above is snapshot in the journal Geometric Approximation http://sarielhp.org/papers/04/survey/survey.pdf via Coresets .I could not figure out what is ...
1
vote
1answer
60 views

finding discrète coordinate of Intersection of two convex polygon?

I seek for cartésien coordinate of vertex's of the intersection area between two polygons ? We have two convex polygon's P & Q such that : all vertex of P (resp. Q) are in 2D cartésien plane. I ...
6
votes
0answers
49 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
1
vote
1answer
34 views

How to find the center of mass (not vertex average) of a convex hull?

I have found results that say that computing the average of vertices of a polytope presented by inequalities is a #$P$-hard problem. However what if we want the true center of mass (determined by ...
1
vote
0answers
53 views

How many distinct area histograms I can get by partitioning a M x N rectangle?

Given a M x N rectangle r, a partition p of r is a collection of rectangles with area smaller or equal than r that cover r. The histogram of a partition h(p) is the frequency distribution of rectangle ...
0
votes
0answers
47 views

Upperbounding the number of regions induced by a set of unit disks

Following up on a previous question: At least as many disks as regions Given a set $D$ of $n$ same radius disks, embedded in the plane, they induce a number $k$ of connected regions in $\mathbb{R}^2 ...
0
votes
1answer
35 views

At least as many disks as regions

I am looking for reference of proof for the following fact: Given a set $D$ of same radius disks, embedded in the plane, it holds that the number of connected regions in $\mathbb{R}^2 \setminus ...
1
vote
0answers
27 views

Discrete bi-Laplacian

I was wondering whether there exists any kind of literature on the the powers of the discrete Laplacian, in particular the the discrete bi-Laplacian, possibly with weights on the edges. In particular ...
0
votes
1answer
30 views

Determining corners of this convex set

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$? Edit: This is apparently true, see the beginning of ...
0
votes
0answers
23 views

Laplacian discretization for parametric curves

I know how to compute the discrete Laplacian of a graph and of a mesh (the Laplace-Beltrami operator). Is there an analogous definition for the computation of the Laplacian of a parametric curve ? ...
1
vote
1answer
58 views

Discrete Gauß and geodesic curvature

Imagine that you have an n-polygon $S$ and you wanted to calculated the discrete Gaussian or gedoesic curvature. How are they defined? If $p$ is a vertex of $S$ then Gauß-Bonnet suggests that the ...
0
votes
1answer
33 views

What is the fundamental theorem on discrete groups of Euclidean spaces?

I have been reading the book Using Algebraic Geometry by David A. Cox, John Little, Donal O'Shea for a university project. I am not clear as to what exactly in meant by the phrase "the fundamental ...
3
votes
2answers
70 views

Triangulation of hypercubes into simplices

A square can be divided into two triangles. A 3-dimensional cube can be divided into 6 tetrahedrons. Into what number of simplices an n-dimensional hypercube can be divided? (For example, a ...
1
vote
1answer
27 views

Prove that a planar bipartite graph on n nodes has at most 2n−4 edges.

I know that we have to use Euler's formula ( v−e+f=2) but I don't understand how f = e/2.
1
vote
1answer
89 views

How Many Triangles are Created by n Lines in the Plane?

Suppose we are given n lines in the plane in "general position", which in the present case we define to mean the following: A. no 2 lines are parallel or identical B. no 3 lines have common ...
2
votes
1answer
54 views

Euler characteristic of closed surface

Assume that you have a closed surface that can be covered by finitely many triangles. Then $K(p)= 6-val(P)$ where P is a vertex and $val(P)$ the number of edges that lead to this vertex. Now, I am ...
0
votes
1answer
99 views

How to define open and closed functions whose domain or range is a discrete metric space?

I encountered that a function is open or closed in my analysis book [Herbert Amann, 2005], and it illustrates it in this way: A function $f: X \xrightarrow{} Y$ between metric spaces $(X,d)$ and ...
0
votes
3answers
40 views

Is there a theorem or axiom which shows that permutations of step sequences through a lattice graph result in the same destination?

I have been searching for a theorem, lemma, or even an axiom which shows that the permutations of a step sequence in Taxicab Geometry result in the same destination in such a lattice graph. To ...
10
votes
2answers
169 views

Partitioning the plane into three sets each intersecting the vertices of every square with side 1?

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? (I mean all squares of side-length 1, not just those with ...
0
votes
2answers
36 views

Prove that a convex $d$-polytope has at least $d+1$ facets

This seems trivial but I can't come up with a formal proof. I think there should be a way to do this inductively but I can't figure out how$\ldots$ Any help much appreciated
1
vote
1answer
44 views

The number of $(d-1)$-faces in a $d$-polytope is at least $(d+1)$

I have to try to prove the following: Let $V = {v_1,...,v_n} \subset \mathbb{R}^d$ be a point configuration affinely spanning $\mathbb{R}$ (i.e., $\operatorname{aff}(V) = \mathbb{R}^d)$. Let $H$ be ...
0
votes
1answer
56 views

Proof: Minkowski sum polytope implies A and B polytopes

Suppose $A$ and $B$ are convex sets and their Minkowski sum $A+B$ is a polytope. How do you prove that $A$ and $B$ are polytopes as well?
0
votes
0answers
69 views

Are there any four-dimensional shapes in the whole wide world?

I've looked up images of a 4-D (four-dimensional) shape and they looked like there are built by using regular 3-D (three-dimensional) shapes using a regular 3-D shape connected to another 3-D shape ...
1
vote
1answer
49 views

Relative Interiors of polyhedra

***Source article: Magnanti, T. L., & Wong, R. T. (1981). Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3), 464-484
2
votes
1answer
38 views

Does a unipotent transformation preserve covolume?

Let $S\subset \mathbb{R}^d$ and define $v(S)$ to be the volume of the set $(S+\mathbb{Z}^d)\cap [0,1]^d$ (where $[0,1]^d$ is the unit cube $[0,1]\times [0,1] \times...\times [0,1]$). Let $T: ...
2
votes
0answers
19 views

dimension of Weber set and selectope (as a operator)

Let $\Omega$ be a finite set of players. For a selector $\alpha:(2^{\Omega}-\{\emptyset\})\rightarrow\Omega$, we define a marginal value operator as a linear operator $m^{\alpha}$ ...
28
votes
6answers
902 views

Prove Existence of a Circle

There are two circles with radius $1$, $c_{A}$ and ${c}_{B}$. They intersect at two points $U$ and $V$. $A$ and $B$ are two regular $n$-gons such that $n > 3$, which are inscribed into $c_{A}$ and ...
3
votes
0answers
60 views

Number of lines needed to pass through every region of a map

The webpage http://what-if.xkcd.com/113 explores the fewest number of lines needed so that every state in the US has at least one line going through it. (actuallly great circles on a sphere) Can you ...
5
votes
3answers
268 views

On coverings of the complex sphere

Here, everything takes place in $\mathbb{C}^d$ for some $d$, and the sphere $\mathcal{S} = \{\mathbf{x}\in\mathbb{C}^d:\|\mathbf{x}\| = 1\}$. Given $\delta > 0$, consider a collection of vectors ...
0
votes
1answer
46 views

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| <x,y>\leq 1$ for every $x\in X\}$. How to prove that $(X^*)^*=\overline{conv(X\cup\{0\})}$? I know that ...
4
votes
1answer
182 views

Is every finite group of isometries a subgroup of a finite reflection group?

Is every finite group of isometries in $d$-dimensional Euclidean space a subgroup of a finite group generated by reflections? By "reflection" I mean reflection in a hyperplane: the isometry fixing a ...
1
vote
2answers
124 views

Calculating volume of spherical wedge from parallelepiped corner

I am interested in calculating the volume of the intersection of a sphere of radius 1/2 with the corner of a parallelepiped where the angles between each edge is $\pi/3$ and has unit edge length; we ...
6
votes
2answers
68 views

Simplest graph that is not a segment intersection graph

Given a finite collection $S=\{s_1,s_2,\ldots,s_n\}$ of straight-line segments in the plane, their intersection graph $G(S)$ is a graph that contains a vertex $v_i$ for each segment $s_i\in S$, and an ...
0
votes
0answers
44 views

Constrained optimization using a cutting plane on a tetrahedron

Consider the figure below where $(a,b,c,d)$ is a tetrahedron and $p=(1-t)a+tb$ is a point on the $ab$ segment. If $n_a$ and $n_b$ are two unit vectors associated with $a$ and $b$, respectively, then ...