**0**

votes

**0**answers

88 views

### Finding good high-dimensional sphere coverings in Euclidean space

Suppose we want to cover the unit sphere $\mathcal{S}^{d-1} := \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ with spherical caps $\mathcal{C}_{\mathbf{y}} := \{\mathbf{x} \in \mathcal{S}^{d-1}...

**1**

vote

**0**answers

46 views

### computing homology of subvarieties of Euclidean spaces by persistent homology

Let $M$ be a submanifold of the Euclidean space $\mathbb{R}^n$. Let $G$ be a finite group acting on $M$ freely. I want to compute the homology (or even the cohomology ring) of $M/G$.
Suppose the ...

**5**

votes

**1**answer

267 views

### Graph spectra and topology

This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph.
To give an ...

**3**

votes

**0**answers

42 views

### Connectedness of semi algebraic set by c.a.d

I do not know whether there is a standard or some traditional ways to decide whether a semi algebraic set is connected or not.
One way I know is c.a.d algorithm. I have read some papers of c.a.d ...

**5**

votes

**1**answer

180 views

### Ascertain properties of a new kind of rectilinear-convex set

PREABMLE TO MY QUESTION
I am reading about convex sets and hulls in orthogonal/rectilinear spaces. As can be seen in this publication, for a given set of points in $\mathbb{R}^{2}$, there are many ...

**4**

votes

**1**answer

289 views

### How to compute the tangent space of a quotient by a finite group

Let $I\subseteq R:=\mathbb C[x_0,\ldots,x_n]$ be a homogeneous ideal defining a subscheme $X\subseteq\Bbb P^n$. As in my previous question, the permutation group $\mathfrak S_{n+1}$ acts on $R$ by ...

**7**

votes

**3**answers

299 views

### A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...

**1**

vote

**0**answers

70 views

### connectedness of semi algebraic sets

We know the inequalities $x_ix_j >\theta_{ij}$ or $x_ix_j<\theta_{ij}$ for some $\theta_{ij}$>0, some $i,j\in\{1,\cdots,n\}$, $i\neq j$ defines the easiest semi algebraic set in $R^n_{\geq 0}$, ...

**4**

votes

**2**answers

224 views

### (non-)existence of the aperiodic monotile

The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...

**0**

votes

**0**answers

46 views

### Distinguishing (possibly lower dimensional) $1$-skeleton of a regular graph inscribed in a sphere

Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with ...

**0**

votes

**0**answers

27 views

### Equivalence between multiclass SVMs, power diagrams, and constrained $k$-means

Apologies in advance for the long post:
Suppose we have a collection of points $\mathbf{p}_1,\dots,\mathbf{p}_n$ in $\mathbb{R}^d$, and we consider the following three ways of partitioning these ...

**2**

votes

**1**answer

116 views

### Choosing the weights of a Voronoi diagram — is this function always the gradient of another function?

This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...

**1**

vote

**0**answers

51 views

### Covering the annulus of symmetric convex body

Consider a symmetric convex body $A$ in $\mathbb{R}^d$. Now, we draw another object, $A'$, concentric and translated with respect to $A$ and having radius slightly greater than twice to the radius of ...

**1**

vote

**1**answer

64 views

### Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces

Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...

**0**

votes

**0**answers

61 views

### Term for meshes bounding a non-degenerate tetrahedral mesh in 3D?

Is there a term in the literature referring to triangle meshes that are the closed boundary of some non-self-intersecting, non-degenerate tetrahedral mesh embedded in $R^3$?
This class of triangle ...

**1**

vote

**0**answers

108 views

### cohomology ring of compact submanifolds of Euclidean spaces

Suppose we have a compact $m$-dimensional submanifold $M$ of $\mathbb{R}^N$ and we want to know the cohomology ring $H^*(M;\mathbb{Z})$.
Let $\epsilon>0$ and a $m$-dimensional finite simplicial ...

**2**

votes

**4**answers

135 views

### Show that the Minkowski sum of two triangles in 3D is the union of Minkowski sums of each triangle along the other's edges?

I'd like to show (or disprove) the claim that the Minkowski sum of two triangles with vertices in $\mathbb{R}^3$, $A+B$, is equal to the union of the unions of the Minkowski sums of $A$ along all ...

**5**

votes

**2**answers

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

**5**

votes

**0**answers

154 views

### Determining N d-points yielding equal sums of Euclidean distances from M s-points

Given M source points (s-points), determine N, the number of destination points (d-points), and their locations (coordinates), such that the sum of the N Euclidean distances from each source point to ...

**0**

votes

**0**answers

69 views

### conformal deformation with fixed boundaries

For a flat plane with certain boundary, e.g., a rectangular patch, is it possible to conformally displace or deform such patch to a curved bump with exact same boundary? In this thesis, Dr. Keenan ...

**1**

vote

**0**answers

54 views

### VC dimension of infinite cones [closed]

What is the VC dimension of infinite $d$-dimensional cones? ( single cones not double).
I would say $2d + 1$ or $O(d^2)$
Does anybody have any reference or ideas?

**0**

votes

**0**answers

26 views

### Efficient sampling from a polytope with large number of contraints [duplicate]

As far as I know, the most popular way to sample from a polytope (in H-representation)
\begin{equation}
\mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\}
\end{equation}
...

**0**

votes

**0**answers

65 views

### Maximum value of linear function on the intersection of a parametrized family of balls

Let $C$ be a (nonempty) closed convex subset of $\mathbb{R}^n$ and $a, b \in \mathbb{R}^n$. Using the normal cone characterization of the euclidean projection operator $\mathrm{proj}_C$ (recall that $\...

**2**

votes

**0**answers

66 views

### Natural neighbor interpolation

Recently I am interested in Natural neighbor interpolation, that is :
Given a function $P(x)$ and some interpolation points $\{x_i,P(x_i)\}_{i=1}^N$, we have the interpolation function $$P^*(x)=\sum_{...

**1**

vote

**0**answers

71 views

### Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb R^2$...

**-2**

votes

**2**answers

133 views

### Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull) [closed]

Edit : Consider giving a reason for down vote.
In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-...

**2**

votes

**0**answers

84 views

### Finding generators of symmetric cones

I have a bunch of vectors $\mathbf v_i$ in $\mathbb R^n$. I would like to consider the cone $C$ spanned by these vectors, together with all the other vectors that can be obtained by permuting the ...

**1**

vote

**0**answers

41 views

### Uniqueness of Riemann Constant Vector Solution

Let $X$ be a compact, genus $g$ Riemann surface (given as the desingularization and compactification of a plane algebraic curve), $J(X)$ its Jacobian, and $A : X \to J(X)$ the Abel map
$$A(P) = \left(...

**2**

votes

**1**answer

61 views

### Maximal opening angle of a polygon from a point [closed]

I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point.
One ...

**6**

votes

**1**answer

163 views

### Algorithm that generates a n-simplex that cover n-polytope?

Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?

**3**

votes

**1**answer

113 views

### The circle with minimal radius covering known finite set of points on a plane

Given some points on a plane, how to determine the circle with minimal radius covering all these points?

**6**

votes

**2**answers

240 views

### Do computational geometers use Lagrange multipliers?

Can anyone point me to an example of a problem that (more or less) originated in computational geometry whose solution requires the use of Lagrange multipliers (or Kuhn-Tucker conditions, or dual ...

**0**

votes

**1**answer

98 views

### Detect perimetral edges of a polygon [closed]

I'm developing a building editor. Users can draw rooms by adding angles (vertices of the room) with a left click. Clicking on an existing angle closes the room and fills the floor by using the ...

**4**

votes

**1**answer

145 views

### Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...

**4**

votes

**1**answer

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

**1**

vote

**0**answers

80 views

### Epsilon-net of operator norm ball around Identity

Suppose I look at the set of matrices which are invertible and satisfy
$$
\left\|A-Id\right\|_{op}<r
$$
for some $r<1$, where $Id$ is the $n\times n$ identity matrix. An $\epsilon$-net of such ...

**4**

votes

**2**answers

443 views

### Breaking a rectangle into smaller rectangles with small diagonals

Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...

**5**

votes

**0**answers

150 views

### Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell

Given an $n \times n$ grid with unit grid cells, and one point from the interior
of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...

**4**

votes

**2**answers

78 views

### Expressing a convex Polytope as a sublevel set of a function

Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to \...

**5**

votes

**2**answers

764 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

**0**answers

254 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

338 views

### What are the applications of Voronoi diagrams in pure mathematics? [closed]

Voronoi diagrams have interesting mathematical properties and applications in algorithms and modeling. But what are its applications in pure mathematics? For example, what theorems can be proved using ...

**7**

votes

**1**answer

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

**4**

votes

**2**answers

177 views

### Construct polygon/polyhedron containing all points not externally visible w.r.t given polygon/polyhedron?

Is there an algorithm to construct a polyhedron containing all points in space for which there exists no ray to infinite not intersecting a given polyhedron?
In 2D, we could consider polygons. For ...

**4**

votes

**1**answer

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

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

**3**

votes

**1**answer

445 views

### Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...

**2**

votes

**2**answers

1k views

### Trilateration problem

When trying to develop an algorithm for a program, I got with the following problem:
Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...

**1**

vote

**1**answer

173 views

### Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier

Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...

**9**

votes

**3**answers

841 views

### Is every graph an edge-crossing graph?

Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...