All Questions
Tagged with computational-geometry computational-complexity
22
questions
2
votes
0
answers
65
views
Computational complexity of exact computation of the doubling dimension
Given a finite metric space $X$, the doubling constant of $X$ is the smallest integer $k$ such that any ball of arbitrary radius $r$ can be covered by at most $k$ balls of radius $r/2$. The doubling ...
1
vote
0
answers
44
views
Computational hardness of a discrete generalized rectangle packing problem
I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (...
2
votes
0
answers
193
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
- 2,961
11
votes
1
answer
373
views
Complexity of counting regions in hyperplane arrangements
Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...
- 16.8k
2
votes
0
answers
33
views
Algorithm for lightest unnested planar vertex-disjoint cycle-cover
Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...
- 12.8k
5
votes
0
answers
82
views
special classes of ideals (eg. toric) that admit faster Buchberger algorithm?
I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold:
What are the precise complexity-...
- 1,201
4
votes
1
answer
203
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 469
5
votes
0
answers
86
views
Problem to efficiently compute the Volume of $d$ anchored 4D cuboids
An easy still unsolved special case of Klee's measure problem with applications in multiple objective optimization is described in the following.
Let $[\vec a_1,\vec b_1],\dots,[\vec a_n,\vec b_n]$ ...
- 4,525
1
vote
1
answer
99
views
Estimating volume of a simple object
Volume computation is $\#P$ hard.
Take the $[0,1]^n$ polytope.
Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves.
Volume of bigger section is $\...
- 13.8k
2
votes
0
answers
57
views
Complexity of existence of simple polygonalization with prescribed area?
This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
- 2,961
6
votes
0
answers
233
views
Complexity of scissors congruence?
Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...
- 13.8k
1
vote
0
answers
62
views
Projection of a polytope along 4 orthogonal axes
Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
- 11
7
votes
0
answers
121
views
Does the problem of recognizing 3DORG-graphs have polynomial complexity?
A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...
- 4,525
7
votes
4
answers
702
views
A quick algorithm for calculating the $\ell_1$-distance between two finite sets on the real line?
For two non-empty finite sets $A,B$ in the real line define the $\ell_1$-distance $d_1(A,B)$ between $A$ and $B$ as the smallest Lebesgue measure of a closed subset $\Gamma\subset \mathbb R$ such that ...
- 41.1k
2
votes
1
answer
103
views
What is Known about Preprocessing for Stabbing Queries?
In a concrete setting, I have the following problem:
given a fixed set of simple objects (e.g. disks or, convex polygons with few vertices), I need to quickly report the objects that are hit (i.e. ...
- 12.8k