**0**

votes

**2**answers

272 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

22 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

56 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

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

**2**

votes

**1**answer

202 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

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

**11**

votes

**1**answer

281 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

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

**2**

votes

**1**answer

62 views

### Calculating the “Belvedere Hull” of a Simple Planar Polygon

As an informal motivation the problem, imagine a tower with polygonal footprint, that is located in a beautiful landscape, the "Belvedere Hull" is then related to the directions, in which one would ...

**1**

vote

**1**answer

132 views

### NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
...

**1**

vote

**0**answers

44 views

### Representing a Pullback as an Infinite Matrix

Let $M$ and $N$ be manifolds and let $T: M \to N$ be a bijective map. Let $ \mathcal{F}(M,\mathbb{R})$ (resp.$ \mathcal{F}(N,\mathbb{R})$) be the space of all functions from $M$ (resp. $N$) to ...

**2**

votes

**1**answer

138 views

### Inverse Problem for Pullback

Let $M$ and $N$ be smooth manifolds and $T: M \to N$ be a smooth map. Let $ \mathcal{F}(M,\mathbb{R})$ (resp.$ \mathcal{F}(N,\mathbb{R})$) denote the space of smooth functions from $M$ (resp. $N$) ...

**0**

votes

**1**answer

122 views

### Exploiting the Linearity of the Pullback [closed]

Edit: This question has been significantly revised.
Some recent developments in computational geometry (for example see http://geometry.stanford.edu//papers/fmfrmbs-obsbg-12/fmfrmbs-obsbg-12.pdf) ...

**0**

votes

**0**answers

87 views

### Trilateration issues, when circles don't intersect

I'm working on Indoor localization where I've deployed multiple iBeacons in my environment. I'm taking distances from all the beacons through their RSSI values. They are not 100% accurate though. Now ...

**0**

votes

**2**answers

198 views

### Determine the boundary points of a set of points [closed]

I have a set of points $S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$. Then how to find the boundary points (which is a subset of $S$) of $S$?
There are methods like convex hull, concave hull and ...

**3**

votes

**2**answers

74 views

### Average vertex degree in finite Delaunay triangulations in high dimensions

In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6.
Does anyone know of a similar result in higher dimension? I ...

**1**

vote

**0**answers

42 views

### Non-Convex Polygons with “Antipodal Visibility”

by "antipodal visibility" of planar, simple polygons I mean the following property:
if two points $p$ and $q$ on the polygon's boundary divide the polygon's boundary into two polylines of equal ...

**0**

votes

**1**answer

265 views

### Is there a Gröbner basis analogue that exists for vector spaces?

Suppose I have a coordinate system $t_1,\ldots t_N$ with a lexicographical ordering. Let LT denote choosing the lowest term of a polynomial with respect to this ordering. e.g. LT$(t_1 + t_2)=t_2$.
...

**2**

votes

**0**answers

170 views

### Dissection of a polygon into convex polygons

Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...

**8**

votes

**1**answer

217 views

### Dubins car shortest paths: Decidable?

A Dubins car follows a
Dubins path
in $\mathbb{R}^2$, with constant wheel speed and
limited turning radius.
It is known that the shortest Dubins path in the absence
of obstacles follows circular
arcs ...

**6**

votes

**2**answers

119 views

### Number of edges in linklessly embeddable graphs

Consider graphs over $n$ nodes.
What is the maximum number of edges of a linklessly embeddable graph?
A more general question is the following. Given $\mu$ what is the maximum number of edges of ...

**0**

votes

**1**answer

70 views

### Paper on unit disk graphs

I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?

**2**

votes

**2**answers

87 views

### Complexity of Untwisting Polygons

What is the complexity of the following task:
given a sequence $p_1, ..., p_n, p_1$ that defines a closed polyline in the euclidean plane,
what is the complexity of finding a reordering of the points, ...

**10**

votes

**1**answer

609 views

### Ways to show a system of polynomial equations has no solution

I came across the following system of polynomial equations on $X_1,\dots,X_{m-2}$:
$$
\begin{cases}
2X_{2s}+\sum\limits_{t=1}^{2s-1}(-1)^tX_tX_{2s-t}=0,\quad s=1,\dots,\frac{m}{2}-1,\\
...

**5**

votes

**2**answers

287 views

### Random Vornoi Diagrams (particular measures)

This is my second question about Random Voronoi diagrams, in my first question was given some excellent advice but i was not clear in explaining what i was looking for.
I'm interested to know ...

**8**

votes

**2**answers

638 views

### Random Voronoi Diagrams

I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...

**2**

votes

**1**answer

104 views

### Computable link invariants

I am interested in the following situation: given a braid $B$, it induces a link $L$ in a pretty straightforward way ("glue" the endpoints, like here). For a braid $B$, we know how to represent it in ...

**2**

votes

**1**answer

233 views

### Hilbert function of points in $\mathrm{P}^2$

Let $\Gamma$ be a collection of $d$ points in $\mathrm{P}^2$, and $I$ the graded ideal of $\Gamma$.If
$$
...

**0**

votes

**0**answers

53 views

### Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not.
Which software would you suggest for rigid transformations?
Thank you

**3**

votes

**1**answer

82 views

### Finding a minimum covering of a polygon with interesting shapes

After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...

**2**

votes

**1**answer

88 views

### mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...

**4**

votes

**1**answer

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

**3**

votes

**0**answers

37 views

### Find shift direction for min overlap area of 2 polygons

I have 2 arbitrary polygons (concave or convex) with certain overlap.
Now there is some relative shift between these 2 polygons (vector s with a constant length).
I want to find the direction of s ...

**0**

votes

**0**answers

58 views

### plotting parametrized algebraic curves near singularities

I have a parametrized algebraic curve:
x(t)=A(t)/D(t);
y(t)=B(t)/D(t);
with A(t) and B(t) being polynomials in t. The curve is solution of a linear system in two unknowns x and y with Cramer's ...

**3**

votes

**0**answers

134 views

### Dead Flies Problem [duplicate]

If a set of points in the plane contains one point in each convex region of
area 1, then can it have finite density?
what is the density of the points? In my understanding, it means the average ...

**3**

votes

**2**answers

197 views

### Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...

**3**

votes

**1**answer

75 views

### Number of lattice polytopes contained in a given lattice polytope?

Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?

**5**

votes

**3**answers

294 views

### How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...

**5**

votes

**1**answer

133 views

### Given a polygon with holes, find a maximum distance pair in two subsets

I am curious about the following problem:
Given a polygon with holes and two convex subsets, $S$ and $T$, find points $s \in S, t \in T$ such that the shortest path between the two points has maximal ...

**5**

votes

**1**answer

184 views

### Simultaneous geometric separator

A geometric separator is a line that separates a given set of shapes to two subsets of approximately the same size (up to a constant), while intersecting only a small number of shapes. When a ...

**1**

vote

**1**answer

274 views

### Explicit computation of the action of a Dehn twist on the fundamental group of a surface

Let $S$ be a compact orientable surface of genus $g$. Now let $p\in S$ and $\gamma$ a closed simple curve on $S$ disjoint from $p$. It is not very difficult to compute the action of a Dehn twist along ...

**1**

vote

**2**answers

163 views

### A Claim on Typical Voronoi Cells

I am trying to prove the following claim (may be it has been proven).
Claim: Consider a set of points $\phi=\{x_1,x_2,...,x_i,...\}$ generated by a homogeneous PPP with rate $\lambda$ in the 2-D ...

**3**

votes

**2**answers

213 views

### Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances

Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances.
The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?

**1**

vote

**0**answers

47 views

### Covering a set of points by bounded geometric object/objects

1) Let $S$ be a set of $n$ points in $R^d$. Now, given a bounded geometric object $G$, the problem is to check whether $S$ can be contained in $G$.
2) Also, in general setting, the problem is to ...

**6**

votes

**0**answers

77 views

### Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces

Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...

**1**

vote

**1**answer

67 views

### Smoothly deforming a set of three-dimensional points

I want to deform a 3D mesh according to 3 or more control points, meaning that the transformation is constituted by pre-images $c_i$ and images $c_i'$ of these control points. Each point of the mesh ...

**2**

votes

**2**answers

194 views

### Largest inscribed rectangle inside a convex polygon

It has been proved by Radziszewski in this paper
K. Radziszewski. Sur une probleme extremal relatif aux gures inscrites et circonscrites aux gures convexes. Ann. Univ. Mariae Curie-Sklodowska, Sect. ...

**4**

votes

**1**answer

128 views

### Maximal geometric mean of distances between points on an interval

Suppose I had T points in the interval $[0,1]$. Call them $e_1, \dots, e_T$.
Question 1:
What is a good nontrivial bound on the geometric mean of $$\{|e_i - e_j| : 1 \leq i < j \leq T \}, $$ as a ...

**3**

votes

**1**answer

169 views

### Hamiltonian circuit

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior.
Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...

**3**

votes

**0**answers

256 views

### Intuition behind minimizing the Dirichlet energy of a mapping

What does minimizing the Dirichlet energy of a mapping $\Phi$ achieve intuitively?
Roughly it is the integral (or sum, if discrete) of $|\nabla \Phi(\;)|^2 dV$, with $V$ the volume.
So is it, in some ...