All Questions
Tagged with computational-geometry mg.metric-geometry
164 questions
1
vote
0
answers
48
views
Deployment and dispersion in triangular regions
Definitions (from C. Stanley Ogilvy's 'Tomorrow's Math'):
Deployment: To place a specified number $n$ of points (stations) in a region such that the maximum distance of any point in the region from ...
- 5,979
5
votes
1
answer
491
views
Check if a polygon has an axis of symmetry in $O(n)$ time
Question: Is it possible to check if an $n$-gon has an axis of symmetry in $O(n)$ time?
Note: An $O(n^2)$ algorithm is easy to see: it is easy to check if any given line is an axis of symmetry of the $...
- 5,979
2
votes
0
answers
174
views
Random sets of points and hyperplanes in high dimensions
We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \in\mathbb{R}^d$ selected uniformly at random from the unit origin-centered ball $\mathcal{B}^{d}$.
Consider the random ...
- 1,677
3
votes
1
answer
190
views
On some centers of convex regions based on partitions
These questions are inspired by Yaglom and Boltyanskii's 'Convex figures'.
Winternitz Theorem: If a 2D convex figure is divided into 2 parts by a line $l$ that passes through its center of gravity, ...
- 5,979
5
votes
2
answers
200
views
Fast algorithms for calculating the distance between measures on finite ultrametric spaces
Let $X$ be a finite ultrametric space and $P(X)$ be the space of probability measures on $X$ endowed with the Wasserstein-Kantorovich-Rubinstein metric (briefly WKR-metric) defined by the formula
$$\...
- 41.9k
0
votes
0
answers
42
views
Construct pairs of $n$-dimensional convex bodies with given ratios ($p$) of volumes
Given a dimension $n$ and a number $p \in (0,1)$, to what extent is it possible (in what cases) to construct a convex set $A$--not a hypersphere--and a "snugly" inscribed (InscribedFigure) ...
- 723
6
votes
1
answer
424
views
Probability of intersecting a rectangle with random straight lines
We are given a rectangle $R$ with sides lengths $r_1$ and $r_2$, contained in a square $S$, with sides lengths $s_1=s_2\ge r_1$ and $s_2=s_1\ge r_2$. $R$ and $S$ are axis-aligned in a cartesian plane $...
- 1,677
5
votes
1
answer
388
views
Calculating $n$-dimensional hypervolumes ($n \sim 50$), for example
I have a question regarding efficient and possibly simple algorithms for computing volumes of $n$-dimensional polytopes.
The polytope of concern isn't arbitrary: it is obtained by applying a linear ...
- 51
5
votes
1
answer
156
views
On folding a polygonal sheet
Consider a polygonal sheet $P$ of area $A$ with $N$ vertices (it material is not stretchable or tearable). Let $n$ be a positive integer >=2.
Question: Let $P$ lie on a flat plane. We need to fold ...
- 5,979
0
votes
1
answer
1k
views
Fast way to generate random points in 2D according to a density function
I'm looking for a fast way to generate random points in 2D according to a given 2D density function.
For instance something like this:
Right now I'm using a modified version of "Poisson disc&...
- 121
2
votes
1
answer
192
views
On some optimal containers of a set of points on the 2D plane
Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find
the smallest semicircular region (semidisk) that contains the points
the smallest ...
- 5,979
4
votes
1
answer
211
views
$\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$
I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such ...
- 41
4
votes
2
answers
213
views
Algorithm for reporting all triangles with unique interior point
What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...
- 13.2k
2
votes
1
answer
504
views
Partitioning polygons into acute isosceles triangles
Question: Given an $N$-vertex polygon (not necessarily convex). It is to be cut into the least number of acute isosceles triangles.
Based on this MathSE discussion, one can think of a method to get $\...
- 5,979
7
votes
1
answer
768
views
To minimize the Hausdorff distance between convex polygonal regions
Definition: The Hausdorff distance is the greatest of all the distances from a point in one set to the closest point in the other set.
Question: Given two convex polygonal regions P1 and P2 on the ...
- 5,979
6
votes
1
answer
631
views
On covering convex 2D regions with rectangles
Given a convex 2D region $C$ and a positive integer $N$. We need to cover $C$ with $N$ rectangles such that the sum of the areas of the $N$ rectangles is the least – no further constraints on the ...
- 5,979
2
votes
1
answer
441
views
Build reversed No-Fit-Polygon
I need some robust algorithm to optimally fit one non-convex polygon into another. The destination one can contain holes.
Recently I found scholarly articles on this subject:
One of them describes ...
2
votes
1
answer
110
views
A questions concerning Laguerre/Voronoi tessellations
Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by
$$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |...
user128095
4
votes
2
answers
440
views
largest diameter of intersection of two balls
Two closed balls with a common radius are positioned so that the centre of either ball is on the boundary of the other.
I am interested in the extremal diameter of their intersection, in an arbitrary ...
- 2,350
3
votes
2
answers
381
views
Cone-Torus intersection in 3D
Problem. I have a solid torus and a solid cone in $\mathbb R^3$ and need an efficient algorithm that determines if they intersect or not.
The center of the torus is at a given position $\mathbf p \in ...
- 101
2
votes
2
answers
124
views
Monotonicity for the side lengths of stars inscribed in regular polygons
Fix integers $l\ge 1$ and $n \ge 3$, and let $P_n$ denote the boundary of the regular $n$-sided polygon in the plane. We define a $(2l+1)$-pointed equilateral star to be a cyclically ordered list of ...
- 115
4
votes
2
answers
805
views
Fitting one Polygon in another
I have two Polygons A and B and I want to find the position, rotation and scale of B, so it fits into A and has the maximum Area possible. Also both can be concave.
I did some research but couldn't ...
- 41
6
votes
1
answer
508
views
How many triangulations of a regular octahedron are there, without introducing new vertices?
It is easy to find three triangulations, each consisting of four tetrahedra. Are there more?
- 61
4
votes
1
answer
88
views
Points on lines with prescribed distances to each other
Given three lines $l_a, l_b, l_c$ in $\mathbb {R}^3$ and three positive numbers $a, b, c>0$ I would like to find points $A, B, C$ on $l_a, l_b, l_c$ respectively, such that the side lengths of ...
- 2,286
5
votes
2
answers
294
views
Convex caps with prescribed edges
Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...
- 7,169
10
votes
0
answers
441
views
A new $\ell_p$-metric on the hyperspace of finite sets?
Let $(X,d)$ be a metric space and $Fin(X)$ be the family of all non-empty finite subsets of $X$. For every $n\in\mathbb N$ the elements of the power $X^n$ are thought as functions $f:n\to X$ where $n:=...
- 41.9k
5
votes
0
answers
1k
views
Reach of manifold vs. $C^k$-manifold
The reach $\tau_M$ of a manifold $M$ is the largest number such that any point at distance less than $\tau_M$ from $M$ has a unique nearest point on $M$.
This concept seems quite related to the local ...
- 151k
2
votes
1
answer
280
views
Worst Case Region for a Convex Hull Heuristic
I am currently implementing a heuristic algorithm for planar convex hulls hand would like to know, for which kind of strictly convex region it exhibits worst performance.
I know that there are many ...
- 13.2k
3
votes
1
answer
295
views
Monotone polygons (and polyhedra) with respect to a point
Dear mathoverflow community,
working on a visualization project I encountered a geometric problem, which I have not yet heard about and am interested in solving algorithmically. However a mere hint ...
- 31
6
votes
1
answer
148
views
Does a minimum area disk that is bounded by a cycle $C$ continuously deform in $R^3$ as $C$ moves in $R^3$?
Let $C_1=(v_1,v_2,\ldots,v_{i-1},v_i)$ and $C_2=(v_1,v_2,\ldots,v_{i-1},v'_i)$ be two cycles that are drawn in $R^3$ in the shape of an unknot (not knotted) with straight line segments as their edges (...
- 415
0
votes
1
answer
407
views
Parametrization of polygons and polyhedra [closed]
So, I've got a pretty interesting problem:
I was wondering how one would go about trying to generate every n-gon, or at least parametrize the space of a specific n-gon (say a hexagon) so it's easily ...
5
votes
0
answers
2k
views
Find the axis of symmetry in a point cloud
I have some dataset which describes a spherical cloud of points in 4D space. Actually, the coordinates of the points are the coefficients of unit quaternions, so you get the idea on what the data is ...
- 151
-1
votes
2
answers
640
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-...
- 119
2
votes
1
answer
248
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,...
- 4,049
3
votes
1
answer
495
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?
- 143
5
votes
0
answers
213
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 ...
user71114
4
votes
2
answers
2k
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 ...
- 4,049
5
votes
2
answers
557
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 ...
- 378
2
votes
0
answers
126
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 ...
- 113
8
votes
2
answers
339
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 ...
- 113
3
votes
0
answers
169
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 $...
- 41
0
votes
1
answer
123
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 ...
- 13.2k
6
votes
1
answer
2k
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 ...
- 163
1
vote
2
answers
680
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 ...
- 133
14
votes
2
answers
540
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
$M(M(a,b),M(a,c))=...
- 5,103
0
votes
2
answers
3k
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 $\...
- 17
8
votes
1
answer
1k
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 ...
- 151k
3
votes
1
answer
428
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 ...
- 3,549
5
votes
4
answers
540
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?
...
- 3,059
5
votes
1
answer
251
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 ...
- 3,549