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

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 ...
1
vote
2answers
794 views

Regular vs. Irregular Vertices in a Mesh

Hi everybody, Reading about Geometry Processing, I have realized that people in this area are very interested in regular vertices(degree=6) rather than irregular ones. Can anybody give me reasons ...
4
votes
0answers
402 views

Generating random polygons from a given triangulation of points

Given a triangulation $T$ of a planar set point $S$, we would like to randomly generate a polygon (hamiltonian cycle) $P$. However, it has been proved that Hamiltonian Circuit Problem on maximal ...
5
votes
2answers
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 ...
5
votes
3answers
289 views

What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))?

What is the most general class of metric spaces for which the closest pair of points in any finite subset can be found in time O(n^(1+eps))? I have studied how to do this in O(n log(n)) in the plane, ...
5
votes
1answer
603 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
629 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 ...
2
votes
2answers
1k 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 ...
1
vote
0answers
174 views

Finding equations for projective bundles associated to vector bundles over explicitly given varieties

Suppose I have a projective variety V over a field k. It is given explicitly in terms of homogeneous equations. Moreover, say I have an explicitly given vector bundle E (in terms of a module ...
4
votes
2answers
355 views

Computing places over x in F/K(x)

Let $F$ be a function field of "transcendental degree one" over its full constant field $K$. Let $x \in F \backslash K$. We know the divisor of $(x) = (x) - (1/x)$ in $K(x)$. Could you please give me ...
4
votes
1answer
589 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 ...
3
votes
1answer
3k views

split polygon into minimum amount of rectangles and triangles

Hi is there an algorithm which cuts a polygon into a minimum amount of preferably rectangles and where not possible (e.g. edges) into triangles?
2
votes
3answers
405 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 ...
6
votes
4answers
811 views

How to compute the average distance till intersection within a triangle in R^2?

Lots of simple questions because I am a noob. You are given 3 points in R^2; A, B, C forming a triangle with area > 0. You pick an arbitrary point inside ABC and an arbitrary direction. After some ...