Questions tagged [computational-geometry]
The computational-geometry tag has no usage guidance.
120
questions
2
votes
0
answers
71
views
Enforcing general position in $2d$ linear programming
Let $(x_1, y_1), ..., (x_k, y_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$.
I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear ...
- 1,078
2
votes
0
answers
42
views
Geometric Set Cover Problem and Union Complexity
I have encountered an instance of the Geometric Set Cover problem where the complexity of the union of any subset with size, say k, of m objects is linear with respect to m. I am aware of a well-known ...
- 21
0
votes
0
answers
58
views
kd-tree optimality for orthogonal range search
It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
- 1,177
0
votes
0
answers
19
views
Intersection of cuttings with a new hyperplane in d dimensions
Consider a d dimensional space with $n$ hyperplanes in general position. Based on these hyperplanes $n/r$ cuttings are constructed. If a new hyperplane is given, how many of the $d$-simplices from the ...
- 38
1
vote
1
answer
52
views
Enumerating part of an arrangement
Consider an arrangement of hyper-planes in $d$ dimensional space. Let us say the attributes are $\{A_1, A_2, \cdots, A_d\}$. If there was a constraint on say an attribute $A_i$ of the type $l_i \leq ...
- 38
3
votes
1
answer
127
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 ...
3
votes
0
answers
25
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 ...
- 691
6
votes
1
answer
308
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
23
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 ...
- 21
2
votes
1
answer
232
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
232
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 $...
- 189
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,475
0
votes
0
answers
305
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
69
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
79
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,595
4
votes
1
answer
116
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) =...
- 265
0
votes
0
answers
73
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,143
2
votes
0
answers
34
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,531
0
votes
0
answers
98
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
181
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
461
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,127
0
votes
0
answers
43
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
65
views
5
votes
1
answer
91
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,531
1
vote
0
answers
44
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 ...
- 2,121
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
341
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,531
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,531
2
votes
1
answer
244
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
206
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
135
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
164
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,058
3
votes
1
answer
233
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. ...
- 720
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
55
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.3k
1
vote
2
answers
113
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
73
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,438
7
votes
1
answer
179
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-...
- 265
3
votes
2
answers
156
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
74
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
106
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
446
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
151
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
69
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
632
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$...
- 325
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
62
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