**1**

vote

**0**answers

102 views

### Boundary surfaces in a 3d Voronoi tessellation with obstacles

Let $x_1,\dots,x_n$ be a set of points in $\mathbb{R}^3$ and let $\mathcal{O}_1 ,\dots, \mathcal{O}_m$ denote a set of polyhedral obstacles. What is the name for the surfaces that describe the ...

**6**

votes

**2**answers

351 views

### Intersection of 2 visibility polygons

Let $P$ be a simple, closed and bounded polygon and $p_1,p_2 \in \mathrm{int}(P)$ be two points in its interior. Is it true that the intersection of the visibility polygons of $p_1$ and $p_2$ is ...

**3**

votes

**1**answer

135 views

### The discrete theory of compressible fluids dynamics

I am working on the discrete theory of compressible fluids dynamics, i.e., numerically solving and simulating the compressible fluids , we are interested in the way using discrete exterior calculus, ...

**0**

votes

**2**answers

183 views

### Incidences of quadratic forms and points

Is there anything that is known about what is the maximal number of incidences between quadratic forms and points? I looked at the internet and I haven't found anything that works for something that ...

**1**

vote

**0**answers

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

**3**

votes

**2**answers

354 views

### Questions on Discrete Exterior Calculus in numerial computing

I have several questions about the Discrete Exterior Calculus (DEC) in the numerical method for solving partial differential equation in physics:
(Discrete Exterious Calculus is the newly developed ...

**1**

vote

**1**answer

64 views

### Uniformly sampling the solution space for points where the free termini of two rays, anchored at 3-space points, can intersect

I have two rays, one of length $L_1$ and one of length $L_2$. I anchor these rays, each at one end, on the 3-space points $p_1$ and $p_2$. Assuming that the Euclidean distance between $p_1$ and ...

**3**

votes

**1**answer

168 views

### Triangulation of the surface determined by sampling two of its cross-sections

I have a data set that essentially looks like the picture below, i.e., it's given by sets of points in $\mathbb{R}^3$ that sample the cross-sections of a certain surface that in principle I do not ...

**7**

votes

**1**answer

179 views

### Fractional Helly for more than one piercing

Fractional Helly Theorem says the following:
For every $0<\alpha\leq 1$ there exists $\beta = \beta(d, \alpha)$ with the following property. Let $C_1 , C_2 , ..., C_n$ be convex sets in $R^d$, $n ...

**3**

votes

**1**answer

215 views

### What properties does generalized Delaunay triangulation have?

Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...

**2**

votes

**0**answers

221 views

### Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin

Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them?
Background:
Thanks to Will Jagy ...

**5**

votes

**2**answers

577 views

### Find minimum-area ellipse which encloses two ellipses

I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...

**2**

votes

**3**answers

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

**1**

vote

**2**answers

1k views

### Projection of a point to a convex hull in d dimensions

Hi,
I've got n points in d dimensions (typically n is around 30k-60k and d is 5 or 6). I'm using qhull to calculate the Delaunay triangulation and the convex hull of the set of points.
You can ...

**3**

votes

**2**answers

650 views

### Find longest segment through centroid of 2D convex polygon?

Given a 2D convex polygon P and its centroid C, how do I find the longest line segment passing through C, where the endpoints of the segment lie on the boundary of P?
Intuitively I imagine there ...

**3**

votes

**1**answer

2k views

### Subtract Rectangle from Polygon

I'm looking for an algorithm that will subtract a rectangle from a simple, concave polygon and return a remainder of polygons. If the rectangle encloses the polygon, the remainder is null. In most ...

**0**

votes

**0**answers

257 views

### Determining the simplices in freudenthal triangulation

HI,
I have a doubt on Freudenthal Triangulation. I want to partition a simplex into finer simplices.
The FT gives me the vertices of the simplices which partition my original simplex into ...

**1**

vote

**0**answers

415 views

### Solving 3D equation system (inverse-projecting a triangle)

Please, how is the equation system below named exactly (to search further literature)?
Does it have an analytical solution? If it doesn't, then what could be the fastest numerical method for it ...

**1**

vote

**0**answers

159 views

### Compute generalized pentagram map

Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...

**10**

votes

**3**answers

535 views

### Algorithms in Invariant Theory

Let $V$ be a polynomial representation of the general linear group $\Gamma:=\DeclareMathOperator{\Gl}{Gl}\Gl_n(\newcommand{\C}{\mathbb C}\C)$.
In chapter 4.6 of his book "Algorithms in Invariant ...

**5**

votes

**5**answers

638 views

### Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

A friend asked me to post the following question. He's not an MO user and felt it would be better received if asked by someone who was already known to the community. This is not my area, but I'll do ...

**7**

votes

**1**answer

3k views

### Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.
In other words, I want to ...

**8**

votes

**2**answers

3k views

### Covering a Polygon with Rectangles

I am tyring to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...

**3**

votes

**2**answers

465 views

### The (Sigma) Algebra of Convex Sets

This is a question-by-proxy for a colleague from computer science. I'm sure many people here are already aware that convex decomposition forms an important sub-field of both computational geometry and ...

**2**

votes

**2**answers

698 views

### Decomposing a polygon with holes

It is known that given a polygon $P$ with holes it is NP-hard to find a decomposition of $P$ into convex polygons, s.t. their number is minimized (even if Steiner points are allowed).
I am wondering ...

**1**

vote

**0**answers

183 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

192 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

530 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

321 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

792 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

598 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

636 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

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

**5**

votes

**3**answers

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

**5**

votes

**1**answer

239 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

567 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

136 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

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

**4**

votes

**1**answer

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

**1**

vote

**1**answer

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

**9**

votes

**3**answers

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

**3**

votes

**2**answers

644 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

262 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

542 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

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

**9**

votes

**1**answer

742 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

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