Questions tagged [computational-geometry]
The computational-geometry tag has no usage guidance.
116
questions
1
vote
0
answers
10
views
Is minimum knot crossing number elementary recursive?
One result in knot theory is that link crossing number is NP-hard. Another result is that the equivalence problem for knots and links is elementary recursive. So, given that the equivalence problem is ...
2
votes
0
answers
17
views
Bound on line with minimum zone complexity in a line arrangement
In an arrangement of $n$ (pseudo)lines, the well known Zone Theorem gives a $O(n)$ bound on the complexity of the zone of any given line (for the purpose of this question, the complexity of the zone ...
- 351
6
votes
1
answer
297
views
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene [1988] (https://dl.acm.org/doi/10.1145/62212.62255).
Specifically, I was trying to look at the $1.82$...
- 13
0
votes
0
answers
142
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal polygons. Rapport showed that it is NP-complete to to decide the existence of orthogonal simple polygon that passes ...
- 20.8k
0
votes
0
answers
20
views
Complexity of the vertices of a decomposed simple polygon to its cells
Given a simple polygon (without holes), consider a given decomposition of the polygon into convex sub-polygons. Suppose there are a number $m$ of convex sub-polygons and the number of the vertices of ...
2
votes
1
answer
174
views
VC dimension of the class of all polygons with k vertices
VC dimension of the class of convex polygons with $ k $ vertices is known to be $ 2k + 1$.
For the general case I was able to derive a bound of the type $ O(k^2log(k)) $ (probably can be easily ...
- 201
1
vote
0
answers
48
views
Partition points in the plane
Given $n=2k$ points in the plane and also given positive real value $r$. Is there an algorithm that partition points into two groups $G_1$ and $G_2$ such that each group contains exactly $k$ points ...
- 11
4
votes
1
answer
220
views
Binary Trees for Nearest Neighbor Search
Given points $x_1, ..., x_n \in \mathbb{R}^d$, consider a binary decision tree $T$ on $\mathbb{R}^d$ with $L$ leaves, i.e. for a point $y \in \mathbb{R}^d$ at every node of the tree, we check whether $...
- 179
5
votes
1
answer
107
views
Finding planes from their points
Given some points $P=\{x_1,\dots,x_m\}$ in a vector space $(Z/2Z)^n$, if $P$ is a union of linear subspaces all of the same dimension $1<d<n$, can we efficiently find these subspaces?
(Any ...
- 4,445
0
votes
0
answers
304
views
A problem in understanding an algorithm
I read a paper from John Hershberger with this title: "Minimizing the sum of diameters
efficiently". That paper proposed a simple algorithm that finds a bipartition of points $S$ in the ...
- 194
1
vote
0
answers
67
views
How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?
I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
- 119
4
votes
0
answers
76
views
Complexity of detecting general position in the plane?
What is the complexity of detecting whether a given set of points in the plane is in general position? This surely must have been studied, but a quick search turns up nothing. For concreteness, let'...
- 9,545
4
votes
1
answer
114
views
A counter example for the set mean objective
Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function
\begin{align}
cost(\mathcal{P},c) =...
- 266
0
votes
0
answers
72
views
"Fast" approximation algorithm for geometric hitting set of same-height rectangles
In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects.
...
- 2,113
2
votes
0
answers
33
views
Complexity of best folding of a 2D set (or how to optimize a sandwich)
Motivation:
I was making lunch for my son, part of which is making a sandwich from two halves of a slice of bread. In order to minimize the parts of bread that have cheese on them, and are not covered ...
- 5,511
0
votes
0
answers
97
views
How many maximal planar graphs are there?
We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
- 1
-2
votes
1
answer
176
views
How to calculate complexity in a high dimensional space?
Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.
For a specific f(), I'm defining a term '...
- 55
18
votes
0
answers
458
views
In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?
Decision Problem
Input: An $m$ by $n$ Boolean matrix $M$.
Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
- 5,025
0
votes
0
answers
42
views
What is the best way to find circles that contain a given point (in 2D)?
Given $n$ circles all with radius $r$ and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions.
...
- 137
0
votes
1
answer
64
views
5
votes
1
answer
89
views
Complexity of computing the union of H-polytopes in three dimensions
Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex).
We are also given a target ...
- 5,511
1
vote
0
answers
43
views
Practical worst-case polylogarithmic dynamic orthogonal range queries?
There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures ...
- 1,921
5
votes
0
answers
92
views
Optimal point placement on integer lattice
What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute
\begin{eqnarray*}
\mu_1(N,n)\triangleq\min_{\mathcal{P}\...
- 51
-1
votes
1
answer
289
views
Example of Delaunay Triangulation where it does not minimize the maximum angle
I know that that the Delaunay triangulation maximizes the minimum angle of triangulation.
And it does not minimize the maximum angle. If we consider the set of points in general position(no four ...
- 1,361
5
votes
0
answers
75
views
Computing 3D viewpoint of a set of non-intersecting segments
Consider the following problem: we are given a finite set of bounded line-segments in ${\mathbb R}^3$, and we want to decide whether there exists a point $p\in {\mathbb R}^3$ from which no two ...
- 5,511
2
votes
1
answer
223
views
How to choose good diagonals when partitioning an orthogonal polygon into rectangles?
Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to ...
- 123
3
votes
1
answer
198
views
Convex polygons inclusion relation
I have the following problem which came as a subproblem in some work I was doing and I am completely stuck.
Note that I am interested in it only in terms of worst case time complexity (not heuristics ...
- 41
2
votes
1
answer
126
views
Data structures for embedded simplicial complexes
I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar ...
- 215
1
vote
1
answer
161
views
The decision procedure of theory of closed real field is in NP-hard?
The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
- 1,050
3
votes
1
answer
214
views
Minimal number of hyperplanes needed to separate sets of points from one other set
Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$.
We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
- 690
0
votes
0
answers
51
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}$
-...
- 11
4
votes
0
answers
53
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? ...
- 10.2k
1
vote
2
answers
112
views
Embedding a n-tree into a b-dimensional space
Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v_n\in \mathbb{R}^m$ (From the current Yuri's reply, m cannot be $...
- 175
1
vote
0
answers
71
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 ...
- 9,398
7
votes
1
answer
176
views
Reference request: Shortest homotopic curve via vertex releases
Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic ...
- 171
0
votes
0
answers
33
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-...
- 266
3
votes
2
answers
153
views
Data structure for radial orderings of points on the plane
Assume points are always in general position.
For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$.
Consider shooting an ...
- 4,367
3
votes
0
answers
73
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 ...
- 181
1
vote
0
answers
101
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 \...
- 21
3
votes
1
answer
380
views
Select circle with given radius that contains most points
Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points.
I tried solving ...
- 31
1
vote
0
answers
80
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 ...
- 992
2
votes
1
answer
150
views
A least sized partition of a set under a distance metric
What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows:
Input:
A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are ...
- 107
5
votes
0
answers
63
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 ...
user17918
12
votes
1
answer
624
views
Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?
Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$...
- 317
1
vote
1
answer
55
views
Inclusion probability of irregularly shaped polygon
I have two shapes, one is a circle, let's call it Circle A, and another irregularly shaped Polygon B. A will always have a greater area than B. Both of these polygons exist inside an area S.
My task ...
- 113
2
votes
0
answers
61
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 ...
- 143
2
votes
0
answers
53
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 ...
- 1,050
2
votes
0
answers
53
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 ...
- 305
-1
votes
1
answer
118
views
given a set of $n$ points in $d$-dimensional space and the basis vectors of some subspace, how to find all the points on that space?
given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k<d$ basis vectors of a subspace $K$ of $\mathbb{R}^d$, is there an efficient algorithm that returns all points from $...
-1
votes
2
answers
156
views
How to continue this algorithm? [closed]
I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º).
I have thought about ...
- 109