Using computers to solve geometric problems. Questions with this tag should typically have at least one other tag indicating what sort of geometry is involved, such as ag.algebraic-geometry or mg.metric-geometry.

learn more… | top users | synonyms

4
votes
0answers
159 views

Upper bounds on art gallery problems using independent witnesses

Given a polygon $P$, the art gallery problem looks to find a smallest set of points that sees all of $P$. One way of bounding the number of guards necessary (from below) is to find a largest set of ...
2
votes
1answer
123 views

Inverse Problem for Pullback

Let $M$ and $N$ be smooth manifolds and $T: M \to N$ be a smooth map. Let $ \mathcal{F}(M,\mathbb{R})$ (resp.$ \mathcal{F}(N,\mathbb{R})$) denote the space of smooth functions from $M$ (resp. $N$) ...
5
votes
3answers
2k views

Random Sampling a linearly constrained region in n-dimensions…

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
6
votes
2answers
860 views

Conic hulls and cones

Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...
5
votes
1answer
611 views

Algorithm for embedding a graph with metric constraints

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide if there is an ...
8
votes
2answers
622 views

Random Voronoi Diagrams

I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...
4
votes
2answers
208 views

point in polytope

Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
1
vote
3answers
4k views

Get a point inside a polygon

I have a 2D polygon of arbitrary geometry. I need to find any point that is inside of that polygon. Taking the center won't work, because the polygon might not be convex. Is there a way to quickly ...