All Questions
62 questions
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
2
votes
1
answer
115
views
Covering the annulus of d-cube
Given a convex body $C\subset R^d$ and a positive real $\lambda$, any set of the form $\lambda C + x = \{ \lambda c+x \mid c\in C \}$, for some $x\in R^d$, is called a homothetic copy of $C$. The ...
- 285
1
vote
0
answers
57
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 ...
- 285
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
1
answer
323
views
What properties does generalized Delaunay triangulation have?
Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
- 18.9k
10
votes
1
answer
9k
views
Get Largest Inscribed Rectangle of a Concave Polygon
I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.
In other words, I want to ...
- 325
12
votes
2
answers
11k
views
Covering a polygon with rectangles
I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...
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
vote
1
answer
3k
views
Covering an arbitrary polygon with minimum number of squares
I have a problem whereby, given an arbitrary polygon with any number of points, I need to cover the whole area by a number of fixed size squares. I can easily find a set of squares which covers the ...
- 51
16
votes
2
answers
5k
views
Weighted area of a Voronoi cell
Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
- 195
3
votes
1
answer
386
views
Pointers/Papers on subdivision of planar quadrilateral meshes (PQ-Mesh) in 3D?
I'm interested in the subdivision of planar quadrilateral meshes (PQ-Meshes). Meshes consisting only of planar quadrilaterals, like discrete Voss surfaces and alike. I've been searching the web
for ...
- 133
15
votes
3
answers
9k
views
$n$-dimensional Voronoi diagram
I need to compute the Voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind it;
b)...
- 253