**0**

votes

**1**answer

37 views

### Complexity of Untwisting Polygons

What is the complexity of the following task:
given a sequence $p_1, ..., p_n, p_1$ that defines a closed polyline in the euclidean plane,
what is the complexity of finding a reordering of the points, ...

**3**

votes

**1**answer

173 views

### Ways to show a system of polynomial equations has no solution

I came across the following system of polynomial equations on $X_1,\dots,X_{m-2}$:
$$
\begin{cases}
2X_{2s}+\sum\limits_{t=1}^{2s-1}(-1)^tX_tX_{2s-t}=0,\quad s=1,\dots,\frac{m}{2}-1,\\
...

**5**

votes

**2**answers

270 views

### Random Vornoi Diagrams (particular measures)

This is my second question about Random Voronoi diagrams, in my first question was given some excellent advice but i was not clear in explaining what i was looking for.
I'm interested to know ...

**8**

votes

**2**answers

596 views

### Random Voronoi Diagrams

I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...

**2**

votes

**1**answer

87 views

### Computable link invariants

I am interested in the following situation: given a braid $B$, it induces a link $L$ in a pretty straightforward way ("glue" the endpoints, like here). For a braid $B$, we know how to represent it in ...

**2**

votes

**1**answer

220 views

### Hilbert function of points in $\mathrm{P}^2$

Let $\Gamma$ be a collection of $d$ points in $\mathrm{P}^2$, and $I$ the graded ideal of $\Gamma$.If
$$
...

**11**

votes

**2**answers

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

**0**

votes

**0**answers

32 views

### Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not.
Which software would you suggest for rigid transformations?
Thank you

**3**

votes

**1**answer

164 views

### Hamiltonian circuit

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior.
Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...

**3**

votes

**1**answer

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

**0**

votes

**1**answer

55 views

### mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...

**4**

votes

**1**answer

219 views

### “Average” Voronoi diagrams without probability?

A plane Poisson process with uniform intensity scatters "sites" about the plane. If I'm not mistaken, in a sense the "average" Voronoi diagram of that set of sites is a honeycomb. I know it's been ...

**3**

votes

**0**answers

30 views

### Find shift direction for min overlap area of 2 polygons

I have 2 arbitrary polygons (concave or convex) with certain overlap.
Now there is some relative shift between these 2 polygons (vector s with a constant length).
I want to find the direction of s ...

**43**

votes

**2**answers

961 views

### Reasons to prefer one large prime over another to approximate characteristic zero

Background:
In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a large prime $p$, rather ...

**3**

votes

**2**answers

177 views

### Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...

**0**

votes

**0**answers

56 views

### plotting parametrized algebraic curves near singularities

I have a parametrized algebraic curve:
x(t)=A(t)/D(t);
y(t)=B(t)/D(t);
with A(t) and B(t) being polynomials in t. The curve is solution of a linear system in two unknowns x and y with Cramer's ...

**3**

votes

**0**answers

132 views

### Dead Flies Problem [duplicate]

If a set of points in the plane contains one point in each convex region of
area 1, then can it have finite density?
what is the density of the points? In my understanding, it means the average ...

**3**

votes

**1**answer

69 views

### Number of lattice polytopes contained in a given lattice polytope?

Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?

**4**

votes

**1**answer

234 views

### Software computation with arithmetic schemes

For rings such as $\mathbb{Z}[x,y]$ is there software to compute any of:
1.) The integral closure of $\mathbb{Z}[x,y]/(f)$. de Jong has a very general algorithm that works in this context ...

**16**

votes

**9**answers

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

**5**

votes

**3**answers

267 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

**1**answer

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

**2**

votes

**3**answers

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

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

**5**

votes

**1**answer

121 views

### Given a polygon with holes, find a maximum distance pair in two subsets

I am curious about the following problem:
Given a polygon with holes and two convex subsets, $S$ and $T$, find points $s \in S, t \in T$ such that the shortest path between the two points has maximal ...

**1**

vote

**1**answer

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

**1**

vote

**1**answer

202 views

### Explicit computation of the action of a Dehn twist on the fundamental group of a surface

Let $S$ be a compact orientable surface of genus $g$. Now let $p\in S$ and $\gamma$ a closed simple curve on $S$ disjoint from $p$. It is not very difficult to compute the action of a Dehn twist along ...

**1**

vote

**2**answers

157 views

### A Claim on Typical Voronoi Cells

I am trying to prove the following claim (may be it has been proven).
Claim: Consider a set of points $\phi=\{x_1,x_2,...,x_i,...\}$ generated by a homogeneous PPP with rate $\lambda$ in the 2-D ...

**3**

votes

**3**answers

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

**3**

votes

**2**answers

193 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$?

**0**

votes

**0**answers

76 views

### minimizing the sum of euclidean norms with box constraints

minimizing the sum of euclidean norms with box constraints
I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...

**1**

vote

**0**answers

90 views

### minimizing the sum of euclidean norms

minimizing the sum of euclidean norms with box constraints
I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...

**1**

vote

**0**answers

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

**1**

vote

**2**answers

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

**6**

votes

**0**answers

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

**1**

vote

**1**answer

61 views

### Smoothly deforming a set of three-dimensional points

I want to deform a 3D mesh according to 3 or more control points, meaning that the transformation is constituted by pre-images $c_i$ and images $c_i'$ of these control points. Each point of the mesh ...

**2**

votes

**2**answers

159 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

**1**answer

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

**19**

votes

**4**answers

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

**3**

votes

**0**answers

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

**2**

votes

**1**answer

239 views

### Regularity of Delaunay triangulation of a hypercube

First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations:
(A)
(B)
We say the lower triangulation is more "regular" than upper ...

**4**

votes

**2**answers

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

**4**

votes

**1**answer

280 views

### Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...

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

**1**

vote

**2**answers

104 views

### Incremental structure of a delaunay triangulation

This would probably be considered a reference request, as I would imagine it has been studied extensively in earlier work. Say I have a collection of distinct points $X = \{x_1,\dots,x_n\}$ in the ...

**3**

votes

**2**answers

383 views

### Hyperrectangle partition of set of overlapping hyperrectangles

I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...

**2**

votes

**1**answer

256 views

### Finding the vertices of a convex polyhedron from a set of planes

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...

**3**

votes

**3**answers

424 views

### How to find the minimum number of hyperplanes to define a convex hull?

I have the following problem:
I have a convex hull $\Omega$ defined by a set of n-dimensional hyperplanes $S = [(n_1,d_1), (n_2,d_2),...,(n_k,d_k)]$ such that a point $p \in \Omega$ if $n_i^T p \geq ...

**3**

votes

**1**answer

113 views

### Number of isomorphism classes of triangulations of a convex polygon

The number of triangulations of a convex $n$-gon is $C_{n-2}$ the $n-2$nd Catalan number. What I am wondering, is if there is a way to enumerate the isomorphism types of these as graphs? I am ...

**3**

votes

**0**answers

70 views

### Computing with Graphs in Surfaces

I asked this question yesterday on math.stackexchange, but the only response so far hasn't really addressed the question, so I thought I'd cross-post it.
I am currently working on a research project ...