# Tagged Questions

**4**

votes

**1**answer

445 views

### Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?

Given a set $S$ of 2D points in the plane there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.
The $LEC$ problem is stated in this way: find a $LEC$ whose ...

**2**

votes

**1**answer

217 views

### Regularity of Delaunay triangulation of a hypercube

First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations:
(A)
(B)
We say the lower triangulation is more "regular" than upper ...

**6**

votes

**2**answers

320 views

### Intersection of 2 visibility polygons

Let $P$ be a simple, closed and bounded polygon and $p_1,p_2 \in \mathrm{int}(P)$ be two points in its interior. Is it true that the intersection of the visibility polygons of $p_1$ and $p_2$ is ...

**3**

votes

**1**answer

185 views

### What properties does generalized Delaunay triangulation have?

Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...

**1**

vote

**0**answers

144 views

### Compute generalized pentagram map

Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...

**2**

votes

**2**answers

490 views

### Decomposing a polygon with holes

It is known that given a polygon $P$ with holes it is NP-hard to find a decomposition of $P$ into convex polygons, s.t. their number is minimized (even if Steiner points are allowed).
I am wondering ...

**8**

votes

**3**answers

745 views

### Complexity of matching red and blue points in the plane.

I'm just asking because I'm curious.
I was seeking references on the following problem, that a friend exposed to me last holidays :
Problem
Given $n$ red points and $n$ blue points in the plane in ...

**1**

vote

**1**answer

459 views

### Graph drawing: unrooted undirected tree graphs with specified edge lengths.

Has Joseph Felsenstein's equal daylight layout been analyzed by the graph drawing community? The following description is taken from his
drawtree
documentation:
"This iteratively improves an ...

**16**

votes

**2**answers

2k views

### Missing document request

I received a request for another long-lost document:
I am wondering if there is any way I
might obtain a copy of
The geometry of circles: Voronoi
diagrams, Moebius transformations,
...