All Questions
16 questions
4
votes
2
answers
219
views
Algorithm for grouping tetrahedra from Voronoi diagram
I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
- 142
2
votes
1
answer
151
views
Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance
We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...
- 1,677
1
vote
0
answers
81
views
Constructive way to optimally cover a compact subset of Euclidean space
Let, $(X,d)$ be a simply connected compact subset of $\mathbb{R}^d$ with non-empty interiorn, let $d$ denote the Euclidean metric, and let $\varepsilon>0$. Is there a way to iteratively select ...
- 5,405
2
votes
1
answer
428
views
Name and Algorithms for a Sparsest Circle Packing
The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...
- 13.2k
5
votes
0
answers
311
views
Biggest (or large) rectangle in a polytope
I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...
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
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
9
votes
2
answers
3k
views
get a point in polygon (maximize the distance from borders)
I have several 2D polygons represented by lists of xy-coordinates of their vertices.
It is needed to get several points inside the polygon so that they lie possibly far from the polygon's borders (...
1
vote
0
answers
60
views
Finding special vectors generated by a matrix
Let $G\in \Bbb Z^{n\times n}$ be a unimodular matrix.
Are there any efficient algorithms to find the maximum norm of a vector $v$ that satisfies $\langle\Delta(v),v\rangle=0$ over all vectors $v\in ...
- 13.9k
5
votes
2
answers
563
views
Covering convex polygons with inscribed disks
The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around ...
- 15.5k
4
votes
0
answers
173
views
On understanding Discrete-Valued Stochastic Processes( time series, panel data )
It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...
- 41
1
vote
1
answer
226
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
...
- 851
4
votes
1
answer
367
views
convex polyhedron in the unit cube
Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
- 165
4
votes
2
answers
1k
views
Polyline averaging
I'm trying to find a method that can take a collection of polylines, each described by a list of connected points on a plane, and find an "average" path through them. The input lines do not loop.
...
- 51
-1
votes
1
answer
502
views
How to formulate such problem mathematically? (line continuation search) [closed]
I have an array of "lines" each defined by 2 points. I am working with only the line segments lying between those points. I need to search lines that could continue one another (relative to ...
- 13
4
votes
1
answer
1k
views
Algorithm for the shortest path through all the points of a 2D cloud
I have an array of points with their coordinates X and Y. Each point represents a bus stop.
I need to sort the points in a sequence by giving them sequence numbers, so that the path from the first to ...
- 61