**4**

votes

**1**answer

1k views

### intersection of convex and non-convex polyhedra

Hi everyone,
I am trying to find the best appropriate way to intersect polyhedra which may be non-convex.
The number of vertices that build the polyhedron is hence always small (up to 20 or so).
...

**6**

votes

**4**answers

716 views

### Shortest Path in Plane

Hi
I thought about the following problem:
Given a polygonal subdivision of the euclidian plane where each of the polygons has a speed associated with it, and given two points s,t, I'm interested in ...

**4**

votes

**3**answers

734 views

### Area-preserving map between rectangles and fat polygons

Are there any well-known continuous area-preserving maps between fat convex polygons and fat rectangles? Specifically, given a fat convex polygon $C$, is there a natural way to choose a fat rectangle ...

**3**

votes

**1**answer

392 views

### Fast approximation for local Delaunay simplex?

Consider a function $f(x)$ evaluated at a set of points $x_j\in\mathcal{D}\subset\mathbb{R}^d$. I'm working on the following type of low order interpolation method. Consider the Delaunay tesselation ...

**2**

votes

**3**answers

2k views

### Formulas for equidistant curves

Hello,
I'm trying to draw on the computer a curve that keeps always the same distance(given as parameter) from a given curve. I know the formula for the given curve. I tried moving perpendicular to ...

**7**

votes

**2**answers

5k views

### Partitioning a polygon into convex parts

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.
I know almost nothing about this subject, so I've been searching on Google ...

**24**

votes

**4**answers

4k views

### Computational software in Algebraic Topology?

I was wondering if there is any good software out there that allows you to do specific computations in algebraic topology. For example:
Create a simplicial complex/set and ask questions about its ...

**13**

votes

**2**answers

958 views

### Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...

**2**

votes

**3**answers

5k 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 ...

**4**

votes

**1**answer

2k views

### Homogeneous system of polynomial equations

Hi all,
Previously I asked a question that currently has no satisfactory answer Least sum squares given constraints on subcomponents
It comes from an engineering problem. I was thinking to formulate ...

**3**

votes

**2**answers

1k views

### Numerical solution for a system of multivariate polynomial equations

Hi all,
I have a system of 6th-order polynomial equations in 4 variables $q_1, q_2, q_3, q_4$ (i.e. polynomials with all the terms such as $q_1^6, q_2^6, q_2^4 q_3^2$):
$P_k(q_1, q_2, q_3, q_4) = 0$ ...

**8**

votes

**1**answer

215 views

### inferring the slope of a digitized line

Given real numbers $a$ and $b$, and an integer $n \geq 2$, let $f(n,a,b)$ be the minimum of $(nint(ja+b)-nint(ia+b)+1)/(j-i)$ (for $1 \leq i < j \leq n$) minus the maximum of ...

**1**

vote

**1**answer

314 views

### Pointers/Papers on subdivision of planar quadrilateral meshes (PQ-Mesh) in 3D?

I'm interested in the subdivision of planar quadrilateral meshes (PQ-Meshes). Meshes consisting only of planar quadrilaterals, like discrete Voss surfaces and alike. I've been searching the web
for ...

**7**

votes

**2**answers

787 views

### The straightest possible path embeddable in a path of polygons

I'm studying a problem involving the sets of discrete curves that can be embedded in a non-trivial polygon, from a source to a target point, as shown below.
Initially my interest was limited to ...

**2**

votes

**2**answers

1k views

### Finding points inside innermost convex hull [closed]

Given a set of points $S$ on the Euclidean plane, Onion Peeling determines the nested set $H$ of convex hulls on $S$. Define an analytical formula on $S$ which produces a point, not necessarily in ...

**6**

votes

**4**answers

657 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 ...

**2**

votes

**1**answer

331 views

### When are nontopological bistellar flips manifold-preserving?

A topological bistellar flip is the term used by Dougherty, Faber, and Murphy to describe a bistellar flip that does not cause any face of a complex to be duplicated. Suppose we consider a ...

**8**

votes

**3**answers

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 ...

**0**

votes

**2**answers

618 views

### Detect if directed cycle is clockwise or counterclockwise in 3D [closed]

I need to check if cycle given by $(x_1, y_1, z_1), (x_2, y_2, z_2), (x_3, y_3, z_3)$ is clockwise or counterclockwise. I have found this answer: Detecting whether directed cycle is clockwise or ...

**5**

votes

**1**answer

484 views

### Intersections of irreducible components

Let $V$ be an algebraic variety (not irreducible) over $\mathbb{C}$, defined by an ideal $I = \{f_1,f_2,\dots, f_n\}$. $V$ is not necessarily pure dimensional. Suppose $V = R_1\cup R_2\cup\dots\cup ...

**3**

votes

**1**answer

438 views

### Algorithm for Ham Sandwich with Points

I just recently learned the Ham Sandwich Theorem in my algebraic topology class. If we take the measure to be the counting measure and let $n=2$, then the theorem tells us that given a set of black ...

**1**

vote

**1**answer

2k views

### Detecting whether directed cycle is clockwise or counterclockwise

Given a directed cycle in the plane I need to walk it and detect whether it is clockwise or counterclockwise.
My first idea is to gather the sum of the turn angles, where a "left" turn is a negative ...

**2**

votes

**2**answers

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 ...

**1**

vote

**1**answer

155 views

### Open questions in mesh generation

A mesh is a discretization of a geometric domain. An unstructured mesh is typically a triangulation. Unstructured meshes are catching up especially in the academic community.
I'm looking for open ...

**2**

votes

**2**answers

319 views

### formulate edge length problem as convex optimization problem

I want to us convex optimization to describe a problem in computational geometry.
Let $E = (E_1, E_2,\ldots , E_m) $ be a sequence of line segments in the plane, where $E_1$ and $E_m$ may be points ...

**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,
...

**16**

votes

**1**answer

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

**2**answers

936 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 ...

**2**

votes

**3**answers

834 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.

**4**

votes

**0**answers

408 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

**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 ...

**5**

votes

**3**answers

305 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

**1**answer

614 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 ...

**6**

votes

**1**answer

732 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

**2**answers

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

**0**answers

175 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

**2**answers

357 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

**1**answer

608 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

**1**answer

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

**3**answers

411 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

**4**answers

836 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 ...