**1**

vote

**0**answers

68 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

**1**answer

273 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

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

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

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

**1**

vote

**1**answer

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

**5**

votes

**1**answer

218 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

60 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

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

**1**

vote

**0**answers

52 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

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

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

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

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

**5**

votes

**0**answers

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

**5**

votes

**1**answer

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

**-2**

votes

**2**answers

123 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

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

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

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

**3**

votes

**1**answer

110 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

239 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

88 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

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

**1**

vote

**0**answers

77 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

76 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

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

429 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

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

**4**

votes

**2**answers

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

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

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

**12**

votes

**0**answers

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

**9**

votes

**3**answers

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

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

**2**

votes

**0**answers

117 views

### Intersecting balls with convex regions and a bisector thereof

This question is related to my previous posting
Angle subtended by the shortest segment that bisects the area of a convex polygon
Let $C$ be a convex region in the plane and let $s$ be the shortest ...

**1**

vote

**0**answers

49 views

### Concise disambiguation of Voronoi boundaries

Say that $x_1,\dots,x_n$ are points in the plane, with a Voronoi diagram $V_1,\dots,V_n$. The Voronoi diagram is typically defined by $$V_i = \{x:\|x-x_i\|\leq \|x-x_j\|~\forall j\}~.$$ Is there any ...

**6**

votes

**1**answer

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

**2**

votes

**0**answers

100 views

### Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)

Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of ...

**0**

votes

**2**answers

368 views

### algebraic topology and 3d/4d printing [closed]

I googled for papers on applying algebraic topology to 3d/4d printing. It just seems to me that there has to be a connection. Any help, kind audience?
edit: 4d printing means 1-parameter families of ...

**1**

vote

**0**answers

38 views

### Determining feasibility of specific intersection structures between closed paths in the plane

I have two arrays, each containing a different ordering of the same set of integers. Each integer is a label for a point in which two closed paths intersect in the plane. The two arrays are ...

**2**

votes

**1**answer

62 views

### What is Known about Preprocessing for Stabbing Queries?

In a concrete setting, I have the following problem:
given a fixed set of simple objects (e.g. disks or, convex polygons with few vertices), I need to quickly report the objects that are hit (i.e. ...

**0**

votes

**1**answer

101 views

### Practical Algorithm for Comparing the Discrepancy of Point Sets (on Unit Hyper Spheres)

I have devised a simple geometric algorithm for generating a sequence of points on unit hyper spheres; that algorithm depends on a single real parameter, which I would like to optimize in order to get ...

**3**

votes

**1**answer

614 views

### Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...

**1**

vote

**2**answers

295 views

### Regular paths along surface of sphere

I'm trying to create a program where a small ball is supposed to move along the surface of a sphere, which is given by its radius $r$ and the center $c$.
The movement should be repetitive, so that ...

**14**

votes

**1**answer

342 views

### Are all well behaved “mean” functions on $\mathbb{R}^+$ equivalent?

Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties:
$M(a,a)=a\qquad$ (identity)
$M(a,b)=M(b,a)\qquad$ (commutativity).
and possibly
...

**7**

votes

**0**answers

136 views

### Nearest Point to a real algebraic set

Suppose I have a compact bounded real algebraic (eventually: or analytic or semialgebraic or semianalytic set) $V$ in $\mathbb R^3$ and a point $x\in\mathbb R^3$ not in $V$. How much do we know about ...