All Questions
Tagged with computational-geometry mg.metric-geometry
164 questions
6
votes
4
answers
752
views
Algorithm for k-medians in a convex polygon
Are there any known approximation algorithms or exact solution schemes for the k-medians problem in a convex polygon? That is, placing a collection of points $p_1,\dots,p_k \subset \mathbb{R}^2$ in a ...
15
votes
3
answers
9k
views
$n$-dimensional Voronoi diagram
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 it;
b)...
- 253
2
votes
2
answers
2k
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 (...
- 21
22
votes
2
answers
3k
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,
...
- 25.1k
18
votes
1
answer
2k
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 ...
- 25.1k
3
votes
3
answers
2k
views
Is there a simple criterion to determine if two parallelograms intersect?
Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty?
Note that I do not need to actually find the intersection.
- 979
6
votes
2
answers
1k
views
Light rays bouncing around inside a sphere in d-dimensions
Suppose $S=\mathbb{S}^d$ is a unit sphere in $(d-1)$ dimensional space, with $d=3$ of special interest.
The surface of $S$ is a perfect (internal) mirror.
You stand at point $x$ (not the sphere center ...
- 151k
5
votes
1
answer
796
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 &...
- 3,612
11
votes
2
answers
3k
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}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
- 7,857
4
votes
2
answers
3k
views
Computational geometry, tetrahedron signed volume
Short version: I'm trying to compute the orientation of a triangle on a plane, formed by the intersection of 3 edges, without explicitly computing the intersection points.
Long version: I need to ...
- 143
4
votes
2
answers
2k
views
How can I efficiently determine which side of a line segment is internal to the polygon?
As part of a larger analysis I have a need to break a polygon into it's individual line segments and mark which side is "inside" of the polygon. If your curious this is going to be fed into a big ...
4
votes
1
answer
1k
views
Finding integer points on an N-d convex hull
Suppose we have a convex hull computed as the solution to a linear programming problem (via whatever method you want). Given this convex hull (and the inequalities that formed the convex hull) is ...
- 1,801
2
votes
3
answers
490
views
find the collision of a particle with a swept triangle.
Given there is triangle: V in 3D space that transforms over time t -> t1 to V1, and a static point P is somewhere in 3d space, how can I determine if P ever collides with V, and if so at what value of ...
- 123
7
votes
5
answers
1k
views
How to compute the average distance till intersection within a triangle in $\mathbb{R}^2$?
You are given 3 points in $\mathbb{R}^2$; $A$, $B$, $C$ forming a triangle with area > 0. You pick an arbitrary point inside $ABC$ and an arbitrary direction. After some distance $d$, you will ...
- 171