# Tagged Questions

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.

2k views

### Minimum distance between two arbitrary circles in space?

What is the minimum distance between two arbitrary circles in space? I am working out the problem with Maxima, but I am surprised by how complicated this rapidly turns out to unfold for such a "...
265 views

### Checking if one polytope is contained in another

Hi, I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other. At the moment I am ...
595 views

### Area ratio of a minimum bounding rectangle of a convex polygon

Take a convex polygon $P$ in the plane, and find its minimum area bounding rectangle, $R$. I'm interested in the ratio of the area of $R$ to the area of $P$. The ratio has a minimum of $1$ for ...
137 views

### Known graph/surface invariants that can be extracted from homology over different fields

The $Z_2$-homology of a surface viewed as a simplicial complex allows us to extract interesting invariants from the resulting homology groups. $\beta_0$ is the number of connected components, $\beta_1$...
446 views

### Degree of generators of irreducible components

Let $V$ be a Zariski-closed subset of $\mathbb{A}^n_k$, where $k$ is an algebraically closed field. Assume that $V$ may be defined by polynomials of degree at most $d$ (or to put it otherwise $V$ is ...
274 views

### Finding the “top” or “bottom” vertex of a simplex

A vertex $v$ of a simplex in $\mathbb{R}^n$ is a "top" vertex if there exists a point $p \neq v$ in the simplex with $v \ge p$ (i.e. $v_1 \ge p_1$, ... , $v_n \ge p_n$). Similarly, $v$ is a "bottom" ...
314 views

### 'Reference' request: Program to work with cyclic quotient singularities.

I'm looking for program code to deal with cyclic quotient singularities on normal surfaces. In particular, at the moment I need that given a singularity $p$ like $p=\frac{1}{n}(1,a)$ the code computes:...
1k 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 ...
704 views

### Area of a Convex Polygon (Described via Half-Planes)

The intersection of a collection of half-planes describes a convex polygon, whose vertices can be constructed in $O(n \log n)$ time using a divide-and-conquer approach (e.g., intersect each half-plane ...
266 views

### Minimum separating subdivision in Plane

Hi I was thinking about the following problem: Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine ...
2k views

### How to efficiently vacuum the house

Let $P$ be a polygon (perhaps with no acute angles inside) and let $L$ be a line segment. The segment may move through the area inside $P$ in straight lines, orthogonal to $L$, or it may pivot on any ...
237 views

### Characteristics of locally triangle-free graph

Hi I am given a triangulation $T$ of a set of points $S$ in the plane and a disk $D$ which doesn't contain any triangle. If I now look at the subgraph $G(V,E)$ of $T$ whose vertices are the points ...
262 views

620 views

### Graph drawing: unrooted undirected tree graphs with specified edge lengths.

Has Joseph Felsenstein's equal daylight layout been analyzed by the graph drawing community? The following description is taken from his drawtree documentation: "This iteratively improves an ...
866 views

### Can taking the projective closure of an affine variety increase the degrees of its ideal generators?

Say we have some equations $f_1(x)=0, \ldots f_k(x)=0$ defining a variety $X$ in ${\mathbb C}^n$ (not necessarily a minimal number of generators, and not necessarily of minimal degree), and suppose we ...
3k 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$. ...
193 views

### Which rational subfields are corresponding to the two dimensional subspaces of holomorphic differentials

I implemented the algorithm that Felipe Voloch's suggested in his reply to the question: Subfields of a function field the algorithm is here: Subfields of a function field I considered the ...
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 $r$...
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 ...
293 views

### Computational methods for dealing with geometrically complicated solid boundaries in fluid-air interface problems

Hello, I am a PhD student who does not have extensive computational experience seeking advice from those experienced with computational modelling as to which method would be most appropriate for ...
307 views

### Which data structure should I use for hierarchical T-meshes and PHT-splines?

Recently, I'm working on something about polynomial splines over hierarchical T-meshes, which is basically a rectangular grid that allows T-junctions. I want to do some numerical experiments but I don'...
583 views

### Sequence of polygons containing the shortest path

Hello all, I’m looking at the weighted region problem i.e. trying to find the shortest weighted path across a polygon subdivision, but at this point in my work, I only need to know the sequence of ...
1k 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 ...
2k 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). ...
728 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 ...
780 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 ...
455 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 ...
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 ...
8k 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 ...
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 ...
1k 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 ...
7k 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 ...
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 ...
2k 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$ ...
215 views

512 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 ...
3k 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 ...
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 (...
157 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 ...
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 ...