2
votes
2answers
37 views

Calculating the central point with minimal average distance to other points

I work at an office with colleagues coming from all over the country. Our office is quite centrally located, but some colleagues have to travel quite a lot further than others. I often wondered how I ...
1
vote
1answer
39 views

Interactions between geometry and graph theory.

I'm looking for some nice theories or just exercises, with both geometrical aspects and graph theoretics aspects. Example may include for instance the 4-color theorem or Euler characteristics, maybe ...
2
votes
2answers
31 views

Forming a simple polygon from the extrusion of a polygonal chain

Let's say I have a set of vertices connected by edges to form a polygonal chain. Each vertex may be shared by a number of edges to form various sub-chains. An example is shown below. Each edge has ...
2
votes
3answers
69 views

Having the number 59 for example find $x$ which $x^2$ is closer but lower to the 59. In this case is 7

I don't know how to name this but this is what I would need. ...
2
votes
1answer
49 views

Graph theoretic view on manifold triangulations

To make the question (hopefully) clearer, I reformulated it: Some triangulation $T$ of a smooth manifold $M$ is a piecewise linear manifold, because smooth manifolds are topological manifolds. Such a ...
1
vote
1answer
21 views

Inner angles of an irreducible graph on a sphere

Given an irreducible graph on a ball (a sphere in three dimensions). The inner angles of a triangle, quadrangle and pentagon are smaller than $180^{\circ}$. Could anybody give a proof of this ...
0
votes
1answer
24 views

Irreducible graph on a sphere

I am trying to grasp an article about the kissing problem in three dimensions (Das Problem der dreizehn Kugeln, by K. Schütte and B.L. van der Waerden). The article deals with irreducible graphs on a ...
1
vote
1answer
75 views

The shortest path connecting three points

I have 3 points X,Y,Z, lets call them buildings. I need to find the shortest amount of path that connects the 3 buildings, these buildings can be in any sort of shape and any distance from each ...
2
votes
0answers
37 views

Hypersphere packings from hypercubic graphs?

Consider a $D$-dimensional hypercubic lattice, i.e. a graph $H$ embedded in ${\mathbb R}^D$ where the vertices have integer coordinates $ (x_1,...,x_D) \in {\mathbb Z}^D$ and edges are between all ...
0
votes
0answers
35 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
8
votes
2answers
191 views

Visual illustrations of circle packing theorem?

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. Paper Collins, Stephenson: A circle ...
2
votes
0answers
43 views

Uniqueness of projective plane of order 5

Is there a slick way to see the uniqueness of projective plane (equivalently, an affine plane) of order $5$?
1
vote
1answer
26 views

Is the “smallest” connected graph with $n+k$ edges a trivial generalization of the “smallest” connected graph with $n-1+k$ edges?

Consider a set $P$ of $n$ points in the plane. Using $n-1+k$ line segments, $k\geq 0$, these points can be connected (i.e., the graph in which the points are the vertices and the line segments the ...
1
vote
0answers
29 views

Finding coordinates of nodes in a graph

I have a complete graph in which the edges represent the euclidean distance between the nodes which is known. Assuming a node to be (0,0), I want to find (approximately) the coordinates of other ...
0
votes
0answers
19 views

Detect Regions Described By Lines in Rectangular Coordinates

Need some help from the superior math minds here. This problem is part of a software project. Essentially, I have a Cartesian grid. The user can create lines by plotting points (every 2 points ...
4
votes
1answer
67 views

Random embedding of $K_4$ in the unit square

Suppose I embed $K_4$ (the complete graph on 4 vertices) randomly in the unit square (using the uniform distribution for the positioning of the vertices). $K_4$ is planar, but not any embedding of it ...
0
votes
1answer
50 views

Determine line crossing corner of cuboid and POV of a camera faced towards it, based on the angles in the photo

Say you were to take a picture to a corner of a room with 90 degree angled walls and ceiling. In that picture you'd see three radial lines (the edges of the walls) starting in the same point (the ...
0
votes
0answers
34 views

Determine line crossing corner of cuboid and POV of a camera faced towards it, based on the angles in the photo

Say you were to take a picture to a corner of a room with 90 degree angled walls and ceiling. In that picture you'd see three radial lines (the edges of the walls) starting in the same point (the ...
0
votes
0answers
15 views

examples of Voronoi diagram for which each region of the diagram has at least 3 vertices, on average.

Let us assume P is a set of n points and V is the set of vertices in the Voronoi diagram, E the set of edges. Assume n>=3, not all points collinear. Show that there are examples of P for which the ...
4
votes
1answer
255 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
4
votes
1answer
48 views

Understanding McMullen's Upper Bound Theorem

I'm a computer science student working on a paper regarding constrained delaunay triangulations. I have been searching for a proof regarding the upper bound for the number of triangles in a ...
0
votes
1answer
19 views

How to identify a variable-sized zone by a point given by coordinate?

The Cartesian plane is partitioned into zones of variable sizes. A zone is always a rectangle. For example, a zone can be represented like $x \in (0, 3], y \in (30, 50]$ The range in the Cartesian ...
5
votes
3answers
62 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
0
votes
1answer
40 views

Vertices, Edges and Line Segment intersection points

So, I have a bunch of graph edges defined by start and end vertices i.e. edge = (startVertex, EndVertex). No coordinates i.e x or y points provided. How do I ...
-1
votes
1answer
67 views

find a common plane which contains two points (NP hard?)

In this problem the coordinates of 4 points are given. $p_{0}=(x_{0},y_{0},z_{0})$, $p_{1}=(x_{1},y_{1},z_{1})$, $p_{2}=(x_{2},y_{2},z_{2})$ and $p_{3}=(x_{3},y_{3},z_{3})$ I need to find the ...
4
votes
4answers
80 views

What values can $v-e+f$ attain if $G$ is a planar (non connected) graph?

Let $G=(V,E)$ be a planar graph and choose planar representation. If $G$ is connected, then according to Euler's formula, we have $$v − e + f = 2,$$ were $v$ is the number of vertices, $e$ the number ...
5
votes
0answers
70 views

Shortest closed loop containing all extreme points of a convex set

Suppose $S\subset \mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to\mathbb{R}^2$ is a continuous map with $\Gamma(0)=\Gamma(1)$. Suppose $\Gamma$ passes through all extreme points of $S$. ...
2
votes
0answers
37 views

Puzzle - connecting nodes

This might not be the right stack exchange, so if there's a better place to put it please let me know. I have the following problem. Given the following graph, ignoring X, find all possible ...
4
votes
1answer
56 views

Get from point A to point B efficiently.

This is a question I thought about while crossing the street. Suppose you're standing at the bottom-left corner of a rectangle. Your goal is moving to the the top-right corner, efficiently, ...
0
votes
1answer
60 views

Distance Metric in 4 dimensions $\Bbb R^3\times SO(2)$

The euclidean distance metric, $\sqrt{dx^2+dy^2+dz^2}$, shows the shortest distance between two points in $\Bbb R^3$. What would be the distance metric to show the shortest distance between two ...
0
votes
2answers
219 views

What is wrong with this proof: P = NP using polynomial solution for UHP

I am going to show you a proof for P=NP, please tell me where I am wrong. Working space: Symmetric(the distance from AB is equal to BA) Graph with N nodes and M edges. Goal: find a Hamilton path. ...
0
votes
1answer
70 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
0
votes
0answers
42 views

A Survey on Rota's Conjecture

I am looking for a survey on Rota's Conjecture (1970). I am more interested in geometric aspects of the conjecture and any geometric content related to the conjecture. Any reference would be helpful. ...
0
votes
0answers
21 views

Calculate self-avoiding-filling-polygons

Definition of self-avoiding-filling-polygon In Euclidean graph where each vertex is a point on the $2D$ plane, so the weight of each edge is the Euclidean distance between the vertices. ...
1
vote
1answer
60 views

Find self-avoiding-filling-polygon represented by system of linear equations

In Euclidean graph where each vertex is a point on the $2D$ plane, so the weight of each edge is the Euclidean distance between the vertices. I want to find self-avoiding-filling-polygon from my graph ...
-1
votes
1answer
82 views

Lp optimal solution question

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
0
votes
1answer
41 views

Exact distance geometry problem proof

How can one prove that the degree of each node in a distance graph must be at least four in order to obtain a unique solution to an exact distance geometry problem with sparse distance data? The ...
2
votes
1answer
78 views

Converse of the Euler's formula for planar graphs

Let $G=(V,E)$ be a planar graph. Suppose a planar representation of $G$ has been chosen and that $$v-e+f=2,$$ where $v,e$ and $f$ are the number of vertices, edges and faces respectively. See ...
0
votes
1answer
83 views

Maximum number of points at distance exactly one where distance between points is at least 1

This is the problem in question: Let S = {$x_1,x_2,. . .,x_n$} be a set of points in the plane such that the distance between any two distinct points in S is at least one. Show that there are at ...
0
votes
1answer
35 views

What is this total length

What is the value of the total length of all the edges connecting the vertices of a regular $k$-gon that is inscribed on a unit circle?
0
votes
0answers
35 views

How to show this [duplicate]

Given $15$ lines in the plane, can anyone show that there are at least $3$ of the lines, such that the angle between any two of them is less than $\frac{\pi}{4}$?
1
vote
1answer
115 views

Shortest path calculation

I have a given set of start points, a given set of end points. Each start point corresponds to one endpoint. I have to visit all start points, and then the corresponding end points, in the most ...
0
votes
0answers
73 views

First event in a straight skeleton

Is there a simple geometric criterion to check whether the first event in (the wave propagation of) a straight skeleton is an edge event or a split event? The literature I could find is computational ...
0
votes
1answer
105 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 ...
1
vote
2answers
142 views

How well can we embed graphs with shortest path metric into $\mathbb{R}^2$ with Euclidean metric?

If we take the integer lattice in $\mathbb{R}^2$ and make edges from $(m,n)$ to $(m+1,n)$ and $(m,n+1)$, you get your typical city block street layout, and if we put the shortest path metric on the ...
1
vote
1answer
32 views

Relationships between the tutte polynomial?

What is the relationship between a graph $G_n$ with $2$ vertices joined by $n$ edges and the graph of $C_n$ (complete graphs)? And what is the relationship between their Tutte polynomials? Tutte ...
1
vote
0answers
74 views

What is the tutte polynomial

I am really stuck on how to work out the tutte polynomial so any help would be great thanks. G is a graph with 2 vertices, joined by n edges. How to you show what the tutte polynomial is? And what ...
0
votes
0answers
12 views

How to remove all the parent cycle s in a graphycle 1 => that contain atleast one child cycle?

The following are the points of Cycles:- Cycle1=> {1,2,4,6,7} Cycle2=> {2,3,5,6,7} Cycle3=> {1,3,4,5,6,7} I want to remove the cycle 3 because it contains Cycle 1
0
votes
1answer
108 views

Graph Help - Discrete Math

The vertices indicate where cashiers are located; the edges denote unblocked aisles between cashiers. The department store wants to set up a security system where (plainclothes) guards are placed at ...
4
votes
2answers
84 views

Automorphisms of a structure as a powerful tool for studying the structure

This is just an arbitrary testimony of an often repeated slogan: "The group of automorphisms of a given structure is often a powerful tool for studying this structure." D. Lascar, On the ...