The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
24 views

Graph of polytope and hyperplane

Suppose that $P$ is a compact and convex polytope in $R^d$ and let $G$ be the graph of $P$ ($V(G)$ are the vertices of $P$ and $E(G)$ are the $1$-dimensional faces - for example polyedral graphs are ...
3
votes
1answer
49 views

Geometry textbook

I am planning to take a graduate Geometry course next semester. The preliminary syllabus does not specify any textbook but has the following descriptions: Catalog Course Description: This course ...
1
vote
0answers
41 views

Invertibility of NxN nonnegative matrix with diagonally dominant elements

I have a NxN nonnegative matrix where the diagonal element of any row i is greater than the off diagonal elements, 1 > aii > aij ≥ 0 for j not equal to i . This not a diagonally dominant matrix as it ...
2
votes
0answers
63 views

Understanding the parameterization in QuadCover

In trying to understand the QuadCover algorithm as described by Kälberer et al in http://page.mi.fu-berlin.de/polthier/articles/quadCover/KNP07-QuadCover.pdf, I am stuck on figuring out how to ...
3
votes
1answer
89 views

Poisson point process (PPP) and Voronoi cells

Say we have a homogeneous PPP with rate $\lambda$ in the 2-D plane $\mathbb R^2$. In one realization of the PPP we get the points $\phi=\{x_1,x_2,...,x_i,...\}$. Now we generate the Voronoi cells ...
0
votes
0answers
25 views

A configuration of 4 points on the plane that minimizes the variance of the distances between the points

This is connected to my earlier question: Embedding finite (discrete) metric spaces to Eulidean space as isometrically as possible but now I'm only considering the smallest (non-trivial) case. We ...
2
votes
1answer
48 views

Embedding finite (discrete) metric spaces to Eulidean space as isometrically as possible

Let $X = \{1, 2, 3, ..., k\}$ with the discrete metric (distance is 1 for every pair of points). How can this be embedded into $\mathbb{R}^n$ (with the usual metric) such that the embedding would be ...
2
votes
0answers
59 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
3
votes
1answer
21 views

Cyclic polytope of dimension 4

I don't quite know how to count the number of $k$-dimensional faces of a $4$-dimensional cyclic polytope (http://en.wikipedia.org/wiki/Cyclic_polytope) without using the standard formula. Any advice? ...
1
vote
1answer
78 views

Cover the n-sphere with sub-hemispherical caps

Original Question (answered): Define a cap (x,Phi) to be the set of all points of the sphere that are within an angle Phi of the point x. $ 0 \le \phi < \frac{\pi}{2} $. (define the angle ...
1
vote
2answers
32 views

Proof for the length of the shortest 4-connected path and 8-connected path on a chessboard

I have a chessboard with a square marked with A as in the following figure: $$\begin{array}{|c|c|c|} \hline 8&1&2\\ \hline 7&A&3\\ \hline 6&5&4\\ \hline \end{array}$$ The ...
2
votes
1answer
50 views

Reference for important results in linkage theory and their proofs

Are there books or lecture notes that comprehensively introduce the (geometric/topological) theory of mechanical linkages, as well as important results and their proofs? For instance, Kempe's ...
1
vote
0answers
40 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
4
votes
0answers
72 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...
6
votes
0answers
230 views

Surface integral for a scalar function defined on a discrete surface

Imagine a polyhedral, discrete surface embedded in $\mathbb{R}^3$. Its faces are all triangles. For each vertex, one can compute the discrete mean and Gaussian curvatures and evaluate the sum of ...
0
votes
1answer
84 views

Question related to Desargues' Theorem

The diagram below is one way of drawing two triangles ($\Delta PQR,\ \Delta P'Q'R'$) perspective from a point ($O$), with pairs of corresponding sides meeting at $D, E, F$ as in Desargues' Theorem ...
1
vote
1answer
67 views
11
votes
1answer
421 views

Circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them

I have a serious problem with this problem: Is it possible to Draw circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them !? Any help ...
1
vote
2answers
602 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 ...
0
votes
1answer
99 views

Flip graph of point set [closed]

Is the flip graph of every point set in $\mathbb R^3$ connected? If not, is there a set with an isolated node? Def: For a point set $S$, the flip graph of $S$ is a graph whose nodes are the set of ...
2
votes
1answer
42 views

Filling Ratio of Unit Sphere

Consider the unit sphere $S^n$ in ${\bf R}^{n+1}$. Consider $S(r)$, a union of $r$-balls in $S^n$ which is disjoint and that $S(r)$ has maximum area. Then define $$ c_n\doteq ...
2
votes
1answer
42 views

Simplex with edges of length at least s having smallest circumradius

Is it true that of all $k$-simplices with edge lengths greater than or equal to some parameter $s$, the regular simplex with edge lengths $s$ has the smallest circumradius? Please supply a proof or ...
2
votes
0answers
59 views

Intersection of line with discrete hypercubes in n-dimensional space

I am looking for a method to determine the hypercubes that intersect a line between two points in a high dimensional space. I think what I want is the supercover of a line in high dimensional space. ...
2
votes
1answer
80 views

halving lines through the centroid of a cyclic polygon

Let $A_1, A_2,\ldots, A_{2n}$ be $2n$ points on a circle centered at $O$ with the additional property that the centroid of this set of points coincides with $O$. In other words, the sum of the vectors ...
4
votes
0answers
90 views

Covered 10x10 rectangle with L-shapes trominos

We have given L-shaped trominos and a square of size 10x10. Give a nice proof, that 18 L-trominos is the minimal number with which the square can be covered such that it is impossible to insert one ...
4
votes
2answers
95 views

Regular Pentagon is the Unique Largest Two-Distance Set in the Plane

A two-distance set is a collection of points for which only two distinct distances appear among pairs of points. (That is, the distance between any pair of points is either $x$ or $y$, and these ...
23
votes
4answers
472 views

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
1
vote
0answers
34 views

Weights for degree ordering

Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k\geq 3$. Consider the set $M$ of all monomials of the form $x_1^{i_1}.x_2^{i_2}.x_3^{i_3}$ where each $i_j\in \mathbb{N}$ with $i_j\geq 1$ and ...
7
votes
1answer
107 views

Helly's Theorem for Biconvex Sets

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
0
votes
0answers
30 views

Helly's Theorem for Rectangles

Helly's Theorem states the following. Suppose that $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
4
votes
3answers
253 views

Average degree of convex hull vertices in a Delaunay triangulation

Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
1
vote
0answers
81 views

discrete harmonic extension (an exercise of Grimmett's “probability on graphs”)

I'm struggling with exercise 1.3 in Grimmett's book "probability on graphs". Take $G = (V,E)$ a finite connected graph with given positive conductances $(w_e)_{e \in E}$, and let $(x_v)_{v \in V}$ be ...
3
votes
1answer
50 views

Simple geometry problem on distribution of points in a plane

Consider 6 distinct points in a plane. Let $m$ and $M$ be the minimum and maximum distances between any pair of points. Show that $M/m \ge \sqrt3$. I am more interested in arrangement of these points ...
51
votes
4answers
5k 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 ...
1
vote
2answers
89 views

Approximating Euclidean geometry, restricted to $\mathbb{Q}$

I'm having trouble putting this into a fully coherent question, so I'll give the broad question, then a few bullet points to give you a better idea of what I'm asking. I'm looking for a line of ...
1
vote
0answers
49 views

Weighted graphs to minimise the set of distances

$c_{0}$ to $c_{3}$ are given points of the graph and the corresponding weights are $W_{1}$ to $W_{3}$. The objective is to locate $p_{1}$ and $p_{2}$ to minimise the distances $d_{0}+d_{1}$ and ...
2
votes
2answers
86 views

Discretizing continuous surfaces into semi-regular polygons

I am aware that there have been many works on the problem of discretizing a surface into polygons, however, I wonder if in any work the problem of doing so to get polygons with edges of the same ...
10
votes
1answer
474 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 ...
4
votes
3answers
184 views

Dissecting an equilateral triangle into equilateral triangles of pairwise different sizes

It is know that a square can be dissected into other square such that no two of the squares have the same size. This is the simplest dissection of that kind: Is it also possible to dissect an ...
7
votes
3answers
232 views

Name this polytope

I was wondering what people call a certain type of shape. It is the shape formed by an orthogonal projection of a hypercube along one of its longest diagonals. In other words, fill in the missing ...
0
votes
1answer
39 views

Number of faces of $n$ congruent disks

If I have $n$ disks, all of the same radius, how many faces (i.e. maximally connected regions) can the induced arrangement have? For example for 3 disks, it could have 7 bounded faces, but what is ...
0
votes
1answer
127 views

example that shows that the edge chromatic number may be larger than the maximal degree

What is an example that shows that the edge chromatic number may be larger than the maximal degree ∆ ≤ X’(G)
2
votes
0answers
37 views

Fractional Helly for more than one piercing

Fractional Helly Theorem says the following: For every $0<\alpha\leq 1$ there exists $\beta = \beta(d, \alpha)$ with the following property. Let $C_1 , C_2 , ..., C_n$ be convex sets in $R^d$, $n ...
2
votes
1answer
160 views

Brouwer's fixed point theorem implies Sperner's lemma

I'm looking for a proof that Brouwer's fixed point theorem implies Sperner's lemma. The proof should be understandable by an undergraduate. Thanks in advance!
0
votes
1answer
28 views

Elementary doubt about derivations on Jacobians

Hi I have a small doubt on Discrete Geometry, more specifically the derivation of Jacobian. Say we have a function $x:\mathbb{R}^2\supseteq U \rightarrow \mathbb{R}^3 : (u,v) \mapsto x(u,v)$ Also ...
2
votes
0answers
69 views

Combinatorial Laplacian Spectrum

The spectrum of the combinatorial laplacian is well understood for a square lattice. What about for other lattices? In particular: let $ f: \mathbb{Z}^2 \rightarrow \mathbb{R} $. The usual ...
27
votes
1answer
1k views

Dividing a square into equal-area rectangles

How many ways are there to tile an $n\times n$ square with exactly $n$ rectangles, each of which has integer sides and area $n$? The sequence $C(n)$ begins 1, 2, 2, 9, 2, 46, 2, 250, 37. Clearly ...
3
votes
1answer
163 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 ...
3
votes
0answers
46 views

Optimal way to place a given number of points in a region?

Let $A\subset\mathbb{R}²$ and $n\in\mathbb{N}$ be a given natural number. How to find a finite subset of $A$, $P=${$p_1,...,p_n$} such that $\int_A f_P(x)$ is minimum, where $f_P(x) = ...
1
vote
3answers
322 views

Proving by induction that an equilateral triangle will always be divided into (n+1)^2 small triangles?

I'm working on a proof that looks like this: Let $n$ be a positive integer. Given an equilateral triangle, place $n$ points on each side, dividing the side into $n+1$ equal segments. Use the ...