Questions tagged [computational-geometry]
The computational-geometry tag has no usage guidance.
40
questions with no upvoted or accepted answers
10
votes
0answers
123 views
Which convex polytopes have volumes of polynomial bit-length?
A convex polytope is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The volume computation problem for convex ...
5
votes
0answers
51 views
Inapproximability Results for APX-hard Geometric Optimization Problems
A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to ...
5
votes
0answers
101 views
Structures obtained by gluing simplices
I'm looking for the correct name of geometric structures obtained as follows.
2-structures: A collection $X$ of triangles is a $2$-structure. If $X$ is a $2$-structure and $Y$ is obtained from $X$ ...
5
votes
0answers
236 views
Total time complexity of convex hull problem
The convex hull problem is to compute the facets of the convex hull of finitely many given points in $\mathbb{R}^d.$ By cone polarity it is equivalent to computing the vertices and rays of a ...
5
votes
0answers
71 views
Finding of dimension of algebraic varieties
I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf).
Are ...
4
votes
0answers
47 views
$\ell_\infty$ partially enclosing ball problem
Suppose I have $n$ points in $\mathbb{R}^d$ endowed with the $\ell_\infty$ metric, and I wish to find a minimum-diameter ball that contains some $k$ of these points. What is known about this problem? ...
4
votes
0answers
136 views
Computing Minima of the Projection of a Binary Cube
The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-...
4
votes
0answers
192 views
Voronoi diagram in presence of polygonal obstacle
Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$.
The distance between a point $p \in ...
3
votes
0answers
70 views
Rearranging angles of a convex polyline to make it closed
Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with $R[\alpha]$ the clockwise rotation by ...
3
votes
0answers
100 views
Equivalence of weighted Minkowski sums
Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices.
Furthermore, consider a variant of the Minkowski sum (somehow ...
3
votes
0answers
76 views
Triangular range counting query in poly-logarithmic time
What is the minimal space requirement for
triangular range counting queries in plane
if one wants to process each query in poly-logarithmic time?
In [Goswami et al, 2004]
they preprocess the ...
2
votes
0answers
51 views
Congruency check for set of points in 3D using inertia tensor
You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and ...
2
votes
0answers
48 views
Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?
Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?
And if there is, what is the computational ...
2
votes
0answers
37 views
Lower bound on light spanners in Euclidean space reference
It is well-known that Euclidean space of dimension $d$ has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}\cdot w(MST)$ (see Chapter 14 of Geometric Spanner Network book by Narashimhan ...
2
votes
0answers
124 views
Weighted $l_1$ distance
So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along ...
2
votes
0answers
523 views
Shortest non-crossing geometric paths
I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so ...
2
votes
0answers
177 views
Inclusion of polytopes
Consider the following two system of linear (in)eqaulities:
$S = Ax \leq b;\; Cx = e$
$T = Dx \leq d;\; Gx = g$
How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
2
votes
0answers
70 views
Check whether a point is a vertex of Minkowski sum of polytopes
Given $n$ polytopes
$$\begin{align*}
P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\
P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...
2
votes
0answers
52 views
How to compute the basis
Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and
$W=
\begin{...
2
votes
0answers
210 views
Convex hull of polytopes
Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a
structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,......
2
votes
0answers
37 views
centralized deterministic Spanner construction with low degree and low stretch
Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
2
votes
0answers
170 views
Eulerian Triangulations
Hi i am looking for algorithms to decide whether a planar pointset has a eulerian triangulation i.e. a triangulation that makes every vertex of even degree.
I cam across this page http://cs.anu.edu....
2
votes
0answers
96 views
Worst-case optimal Delaunay algorithm based on spatial sort and walking?
Buchin [2] showed that under "reasonable" assumptions, (polynomial point spread) incremental construction of Delaunay triangulations using the biased randomized ordering of Amenta et al. [1] with a ...
2
votes
0answers
122 views
Tiling a rectangle with weighted cells (min-max problem)
Given a sparse matrix $A[1..n, 1..n]$ containing cells with integer value of either $0$ or $1$, partition it in $J$ non-overlapping axis-parallel 2D rectangles, such that each $1$-cell is covered by ...
1
vote
0answers
53 views
Mapping of entire balls using Locality Sensitive Hashing (LSH)
LSH functions are useful for approximate nearest neighbor search.
They are usually defined, for distance metric $d$ and $c>1$ as follows:
A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
1
vote
0answers
73 views
LSH Probabilistic guarantees
A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have:
$\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and
$\lVert x-y\rVert > cr \quad \...
1
vote
0answers
73 views
Points of a finite set wihtin a ball
I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$.
In particular, I would like to be able to solve the problem of finding all the point ...
1
vote
0answers
88 views
Hausdorff Distance and Convex Hull
Given two sets of points A and B, both in $R^d$, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does ...
1
vote
0answers
86 views
Complexity of Maximum Independent Set (or Vertex Cover) on disk packing graphs
I'm interested in complexity results for Maximum Independent Set (or Vertex Cover) problem over the class of disk packing graphs. Having a set of disks we build a graph that has its vertices at the ...
1
vote
0answers
38 views
Current review on polygon partition problems
Mark Keil(1) provides an extensive survey of polygon partitioning and polygon covering alrogithms. This survey was written in 2000. Is there a more recent survey on this topic?
1
vote
0answers
72 views
Compute basis of vertex set of polytope
I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope.
Formally,
INPUT: a polytope
$$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\...
1
vote
0answers
27 views
Extending Delaunay graphs in d-space
I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space.
...
0
votes
0answers
43 views
Volume computation of special polytopes
I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so.
I know that in general it is #P-hard to compute the volume of $\mathcal{H}$
-...
0
votes
0answers
27 views
Two question regarding coreset construictions
I have two questions regarding coreset construction of clustering problem
In A Unified Framework for Approximating and Clustering Data, a very general framework is given to construct coresets for ...
0
votes
0answers
57 views
Linear time algorithm for projective clustering
There is a lot of work in clustering of high dimensional data. In case of k-means, it is shown here that one can get an $(1+\epsilon)$-approximation in linear time, yielding a PTAS, by random sampling....
0
votes
0answers
21 views
Does optimal fitting flat must pass through the mean of the point set?
I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line.
Project clustering is a natural generalization of k-...
0
votes
0answers
68 views
Trade-off between number of spheres and wasted space in covering a 3d object by spheres
Consider the following optimization problem:
Input: a 3-dimensional "object" $O$.
Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing ...
0
votes
0answers
210 views
Clustering in sublinear time/query
Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy:
1) Minimizing the number of balls that are required to cover all ...
0
votes
0answers
401 views
Rectangular constraints in Delaunay Triangulation without edges within
I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside ...
0
votes
1answer
80 views
Algorithms to classify the geometrical relationship of two 3D-geometries
I have multiple 3D volumes which are represented by their boundaries (set of polygons each represented as a list of 3D-coordinates). I am now looking for algorithms to decide if
volume A is inside ...
