3
votes
1answer
53 views

Finding a minimum covering of a polygon with interesting shapes

After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...
5
votes
3answers
257 views

How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights. Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight? ...
5
votes
1answer
175 views

Simultaneous geometric separator

A geometric separator is a line that separates a given set of shapes to two subsets of approximately the same size (up to a constant), while intersecting only a small number of shapes. When a ...
3
votes
2answers
192 views

Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances. The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
1
vote
0answers
42 views

Covering a set of points by bounded geometric object/objects

1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$. 2) Also, in general setting, the problem is to ...
6
votes
0answers
71 views

Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces

Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...
2
votes
2answers
156 views

Largest inscribed rectangle inside a convex polygon

It has been proved by Radziszewski in this paper K. Radziszewski. Sur une probleme extremal relatif aux gures inscrites et circonscrites aux gures convexes. Ann. Univ. Mariae Curie-Sklodowska, Sect. ...
4
votes
1answer
122 views

Maximal geometric mean of distances between points on an interval

Suppose I had T points in the interval $[0,1]$. Call them $e_1, \dots, e_T$. Question 1: What is a good nontrivial bound on the geometric mean of $$\{|e_i - e_j| : 1 \leq i < j \leq T \}, $$ as a ...
3
votes
0answers
191 views

Intuition behind minimizing the Dirichlet energy of a mapping

What does minimizing the Dirichlet energy of a mapping $\Phi$ achieve intuitively? Roughly it is the integral (or sum, if discrete) of $|\nabla \Phi(\;)|^2 dV$, with $V$ the volume. So is it, in some ...
4
votes
2answers
194 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 ...
3
votes
3answers
394 views

Intersection of Polyhedra

I'm writing a collision detection algorithm, and so far I've been using Joseph O'Rourke's book "Computational Geometry in C" as reference. It outlines an algorithm to determine whether a point is ...
4
votes
0answers
148 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 ...
4
votes
1answer
288 views

Biggest ball included in an intersection of balls

I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ...
0
votes
2answers
232 views

Higher dimensional convex hull

Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as ...
2
votes
3answers
1k views

Intersection of Cones in Three Space

In several branches of applied mathematics the problem arises to describe the intersection of two cones in three space. I have searched and found a few references that discuss the problem for cones ...
1
vote
0answers
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", ...
1
vote
0answers
139 views

Techniques for refining or constraining a Voronoi diagram?

I have a dataset coming from weather stations where each vertex used to generate the Voronoi diagram is the lat/long of the station. As such, each cell represents the area whose weather is being ...
11
votes
3answers
472 views

finding the most-isolated point in a high-dimensional cube

I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find $\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} ...
4
votes
5answers
606 views

Segments of Voronoi Diagrams on smooth manifolds. Are they geodesics?

Let $S$ be a patch of a smooth 2-manifold in $\mathbb{R}^3$, and pick two distinct points $a,\ b \in S$. Let $c$ be the set of points on $S$ equidistant to $a$ and $b$, where distance is defined by ...
8
votes
3answers
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 ...
10
votes
2answers
2k views

Weighted area of a Voronoi cell

Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
16
votes
9answers
2k views

Determine if circle is covered by some set of other circles

Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius ...
7
votes
3answers
2k views

n-dimensional voronoi diagram

Hi, I need to compute the voronoi diagram of a set of points in $R^n$. I'm quite unschooled on the topic, could someone point me to the right references so that I can a) understand the theory behind ...
2
votes
2answers
1k views

Anuloid (Torus) x line intersection

Hi, I need calculate ray (line) intersection with torus for my ray-tracing program (I know, its to graphics, but i need math behind it). I can solve equation of order x^4, but thats too way slow ...
16
votes
2answers
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, ...
16
votes
1answer
1k views

What can be said about the Shadow hull and the Sight hull?

This is a question implicitly raised by Is the sphere the only surface all of whose projections are circles? Or: Can we deduce a spherical Earth by observing that its shadows on the Moon are always ...
5
votes
1answer
590 views

Minimizing variance of distances between points when mean distance is fixed

In Rd, I have n > d+1 points. The mean distance between pairs of points is 1. How can I minimize the variance of the distances (equivalently, the mean squared distance)? I'm mainly interested in d ...
5
votes
1answer
571 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 ...