Questions tagged [computational-geometry]

The tag has no usage guidance.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
120 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
100 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
213 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
46 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
182 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
67 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
99 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
35 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
123 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
513 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
171 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
160 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
121 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
48 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
71 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
80 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
84 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
26 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
55 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
389 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 ...