**7**

votes

**3**answers

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

**5**

votes

**1**answer

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

**-1**

votes

**0**answers

19 views

### machine learning representations of infinite number of periodic points on a 3D space [closed]

Is there any standard procedure (building feature vectors) that could be used to build machine learning models based on discrete and infinite point distributions on a hyperplane (practically 2D 3D), ...

**4**

votes

**1**answer

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

**4**

votes

**2**answers

215 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

45 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

26 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

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

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

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

**4**

votes

**0**answers

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

**0**

votes

**0**answers

58 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

107 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

128 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

388 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

148 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

67 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

51 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

64 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

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

**1**

vote

**0**answers

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

**-2**

votes

**2**answers

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

**2**

votes

**0**answers

82 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

39 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) = ...

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

160 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

107 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

236 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

84 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

140 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

984 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

76 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

422 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

148 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

75 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

730 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

246 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

337 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

185 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

167 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

272 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

380 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

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

**12**

votes

**0**answers

166 views

### Dividing a convex region to minimize average distances

Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...

**2**

votes

**0**answers

95 views

### The intersection of two $l_1$ balls

Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap ...

**6**

votes

**1**answer

144 views

### Angle subtended by the shortest segment that bisects the area of a convex polygon

Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...