**1**

vote

**0**answers

150 views

### Techniques for refining or constraining a Voronoi diagram?

I have a dataset coming from weather stations where each vertex used to generate the Voronoi diagram is the lat/long of the station. As such, each cell represents the area whose weather is being ...

**0**

votes

**0**answers

157 views

### Orientation predicate CG

Shewchuk 97 gives me the orientation of 4 points, by finding the sign of a determinant, where the matrix is composed of the coordinates of the points. So, the signed volume of a tetrahedron, or which ...

**11**

votes

**3**answers

489 views

### finding the most-isolated point in a high-dimensional cube

I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find
$\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} ...

**4**

votes

**1**answer

300 views

### Are point sets of the same order type connected by continuous (order type)-preserving motion?

Given two general position point sets in $\mathbb{R}^2$ of the same size and order type, is it possible to continuously move the points of one set until they coincide with those of the other set in ...

**4**

votes

**5**answers

721 views

### Segments of Voronoi Diagrams on smooth manifolds. Are they geodesics?

Let $S$ be a patch of a smooth 2-manifold in $\mathbb{R}^3$, and pick two distinct points $a,\ b \in S$. Let $c$ be the set of points on $S$ equidistant to $a$ and $b$, where distance is defined by ...

**3**

votes

**3**answers

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

**2**

votes

**2**answers

598 views

### maximum number of shortest path among a set of n triangle obstacles

Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting ...

**2**

votes

**1**answer

773 views

### practical algorithm for constrained triangulation in two dimensions?

I'm looking for an algorithm that is easy to implement in practice (resulting in small amount of code), preferably incremental. As far as I know, the biggest problem with incremental constrained ...

**4**

votes

**1**answer

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

**4**

votes

**2**answers

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

**0**

votes

**1**answer

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

**9**

votes

**3**answers

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

**1**

vote

**1**answer

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

**8**

votes

**3**answers

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

**3**

votes

**2**answers

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

**6**

votes

**3**answers

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

**13**

votes

**1**answer

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

**1**

vote

**1**answer

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

**1**

vote

**1**answer

260 views

### Euclidean neighborhoods on Polyhedral surface

Let $(X, Vertex(X))$ be a Polyhedral surface (defined like in Polthier) , $x_0 \in X$ a vertex. Let $B_\epsilon(x_0)$ the euclidean ball centred at $x_0$ with radius $\epsilon$, $\epsilon > max ...

**10**

votes

**1**answer

532 views

### Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...

**1**

vote

**1**answer

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

**8**

votes

**1**answer

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

**13**

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

**1**

vote

**0**answers

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

**17**

votes

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

**6**

votes

**3**answers

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

**8**

votes

**2**answers

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

**1**

vote

**2**answers

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

**2**

votes

**1**answer

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

**7**

votes

**2**answers

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

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

707 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

717 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

378 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

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

**23**

votes

**4**answers

3k 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

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

**1**

vote

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

308 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

771 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

655 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

324 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

602 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

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