Questions tagged [cg.comp-geom]
Computational Geometry is the study of geometric problems from a computational perspective. Examples of problems include: computation of geometric objects such as convex hulls, dimensionality reduction, shortest path problems in metric spaces, or finding a small subset of points that approximates some measure of the whole set (i.e. a coreset).
249
questions
3
votes
0answers
60 views
Data structure to report points in the intersection of two circles
The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly.
This was solved beautifully ...
3
votes
0answers
70 views
Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor
Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ |...
7
votes
1answer
126 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 ...
2
votes
0answers
58 views
Finding the largest set of points of limited diameter (2)
Problem: Given a set of points $S = \{(x_1, y_1), (x_2, y_2),\cdots,(x_n, y_n)\}$ in $\mathbb{R}^2$ and a distance threshold $\tau$, find a subset of $S$ such that (1) the Euclidean distance between ...
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 ...
17
votes
1answer
428 views
How not to compute the smallest circle enclosing a finite set of circles
Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of ...
9
votes
0answers
304 views
Triangle arrangement problem
Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
2
votes
0answers
95 views
Minimize the product of distances from n fixed points
Given $n$ fixed points $\{p_i\}_{i=1}^n$ in $D$-dimensional Euclidean space $\mathbb{R}^D$, consider the following optimization problem:
$$
\begin{align}
\text{mininize} \ \ \ &\prod_{i=1}^n \...
2
votes
1answer
239 views
What is the proof that visibility graphs can be used to compute the shortest path?
I am trying to understand what the proof is that constructing a visibility graph and searching on can give you the shortest path between two points, avoiding a set of convex polygons. I am trying ...
4
votes
0answers
135 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\}$-...
11
votes
1answer
187 views
Smallest axis-aligned box that contains $k$ points
Input: A set of $n$ points in $\mathbb{R}^3$, and an integer $k \le n$.
Output: The smallest volume axis-aligned bounding box that contains at least $k$ of these $n$ points.
I'm wondering if any ...
5
votes
1answer
138 views
Generalized Priority Queues
I was wondering if there is any literature on the following problem:
Maintain a set $S$ where each element is a function from $\mathbb{R}$ to $\mathbb{R}$ supporting the following operations:
Insert ...
12
votes
1answer
305 views
Partitioning a rectangle without harming inner rectangles
$C$ is an axis-parallel rectangle.
$C_1,\dots,C_n$ are pairwise-interior-disjoint axis-parallel rectangles such that $C_1\cup\dots\cup C_n \subsetneq C$, like this:
A rectangle-preserving partition ...
1
vote
0answers
134 views
Clarification needed on an algorithm for $\epsilon$-net construction for the column space of PSD matrices
I found an algorithm for constructing an $\epsilon$-net for a positive semidefine matrix $A\in[-1,1]^{n\times n}$ which has $rank(A)=d$, described in the paper
The approximate rank of a matrix and ...
6
votes
1answer
303 views
Largest rectangle not touching any rock in a square field
Following this mathematical question, I am interested in the algorithmic question:
Given $n$ points in the unit square,
find the largest area of an axis-parallel rectangle in the unit square
...
2
votes
0answers
69 views
Minkowski decomposition of lattice point cloud
Given two point clouds $A,B\subset\mathbb Z^d$, let $A\oplus B$ be their Minkowski sum, defined as the set $\{ a + b : a\in A, b\in B \}$.
Is there any known result for the following problem?
...
11
votes
1answer
224 views
Compute lowest dimensional polytope from a given set of sign vectors
Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\...
4
votes
1answer
101 views
Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm
Roughly speaking, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.
The algorithm specifies splitting the edges ...
1
vote
1answer
65 views
Far point queries in high dimensions
Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".
This is ...
-2
votes
1answer
77 views
arbitrary segment stabbing query for 2d segments
Store a set of 2d segments S in some data structure. For an arbitrary query 2d segment q, answer a yes/no question in sublinear time: whether q intersect with any segment in S?
If the query is a ...
0
votes
1answer
2k views
VC-dimension of triangles in 2D space [closed]
I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7.
The issue is that, for the case when 4 points lying on a straight line ...
3
votes
1answer
259 views
Sorted intervals query
I'm in search for a data structure which efficiently operates over closed intervals with the following properties:
dynamically add or remove an interval
set, and anytime change, a number ("depth") ...
4
votes
1answer
149 views
Algorithm to find all intersections in set of simplices
What is the fastest known algorithm to report all intersecting pairs amongst a collection of $n$ simplices, each with dimension at most $r \leq d$ embedded in $\mathbb{R}^d$ (for small $d$)?
In the ...
1
vote
0answers
79 views
k closest points that belong to a set
This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind.
I have a set of real vectors:
$$
S = \lbrace v_1, \dots, v_n \rbrace
$$
$...
4
votes
0answers
73 views
Bichromatic all nearest neighbors
Given two finite sets of points, $R, B \subseteq \mathbb{R}^d$, compute a map $f : R \to B$ where:
$f(r) = \text{argmin}_{b \in B} |r - b|$
That is $f(r)$ is the closest point in $B$ to the point $r$...
4
votes
3answers
174 views
Fast high-dimensional K-nearest neighbors
I'm aware of this question
https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm
But it's not the same question as I'm asking. Because, Octree and its generalization are only ...
3
votes
0answers
99 views
$k$th closest pair of points
The problem of finding the pair of closest points in a set of points has been a classical example of divide and conquer technique for some decades now. But I could not find any results on finding $k$...
4
votes
0answers
163 views
Problems in dynamic algorithms in computational geometry
The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as:
Dynamic ...
2
votes
1answer
387 views
Time complexity of d-dimensional convex hull
Consider the convex hull problem in $\Re^d$:
Input: a list of $n$ points $S$ in $\Re^d$,
Output: the vertices of the convex hull of $S$.
What is the best lower bound on the time complexity of ...
1
vote
0answers
100 views
Is there an algorithm that, given a point cloud, infers an optimal wireframe (surface) structure?
I have a point cloud that I would like to convert to a surface, in the form of a wireframe lattice structure.
This means, from a sequence of 3D points (x,y,z), obtaining three 2D matrices X,Y,Z of ...
5
votes
1answer
177 views
Number of points on the interior of the convex hull of a random subset
This question is in regards to the following problem:
Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally ...
3
votes
1answer
99 views
Find all hyperplanes separating unique sets of `k` points
I have a series of n points in d-dimensional continuous space. I want to find a series of hyperplanes such that ...
0
votes
1answer
175 views
Match two Polylines [closed]
As per Image, for a Given polyline P which consists of set of Points {(px1, py2), (px2, py2)}, i want to find to which polyline M1, M2, M3 , it matches the best.
Output : M3 Polyline.
Please provide ...
8
votes
3answers
566 views
Barcode of a graph
Using persistent homology, we can analyze the (topological) shape of a cloud of points using the following three-step method:
convert the point set into a simplicial complex (and there are a few ...
5
votes
0answers
244 views
Practical algorithm for testing whether an edge is Delaunay
I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$.
My assumed ...
5
votes
1answer
111 views
Topological properties of Delaunay triangulations
Do Delaunay triangulations satisfy any extra topological conditions over normal planar triangulations?
In other words, if $T$ is a topological triangulation of the plane, when does there exist points ...
1
vote
1answer
94 views
Is this constrained planar triangulation algorithm $O(m \log m)$?
Background: I am implementing triangle mesh CSG using symbolically perturbed exact arithmetic. One of the required subalgorithms is retriangulating a triangular face $T_0$ of the input mesh cut by ...
6
votes
1answer
226 views
Finding balls that contain a point
Suppose you are given a collection of $n$ balls in $\mathbb{R}^d$, and you want to preprocess them in such a way that you can later query them to find all spheres which contain any test point.
What ...
8
votes
1answer
195 views
Multidimensional arithmetic progression variant
For $\vec{d} \in \mathbb{N}^n$, let $Q(\vec{d}) \subset \mathbb{N}^n$ be the set of vertices of the $n$-dimensional cube scaled in the direction of the $i$-th coordinate by $d_i$, i.e.
$Q(\vec{d} = \{...
2
votes
2answers
108 views
BSP, but with curved surfaces (NURBS? kernelized support vectors?)
Let's say that I wanted to use a BSP not just for partitioning points, but also to define surfaces, i.e. that I have $\mathbb{R}^2$ and I want to be able to continuously map at least some easily known/...
4
votes
1answer
134 views
parameterized algorithms for geometric set cover
Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover?
It is known that set cover problem is $W[2]$ hard when parametrized by the solution ...
7
votes
0answers
295 views
Minimum length cuts needed to remove holes in a polygon
Suppose I'm given a connected polygon in the plane with holes. I can "remove" a hole by drawing a straight line from the boundary of a hole to another boundary (either of another hole, or the boundary ...
3
votes
0answers
184 views
Computing the convex hull of several polyhedra
Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities.
How easy is it to compute an ...
2
votes
2answers
167 views
Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density
Say I sample a set of points $(p_1,p_2,...) \in P$ from a probability distribution $f(x,y)$, e.g. a bivariate normal distribution, such that my sampling process chooses a point in the distribution ...
2
votes
1answer
104 views
Largest embeddable hypersphere given membership oracle
I have a membership oracle to tell me whether a point is inside of some set, S. I would like to find the radius of the largest (origin-centered) hypersphere that is contained in S.
Do you know any ...
7
votes
0answers
104 views
Is there any known result for 1-median problem with negative weights in Euclidean space?
Given a set of $n$ points $v_1,\ldots,v_n$ in $R^d$, find a point $p$
such that $\sum_{i=1}^n w_i d(p,v_i)$ is minimized, where $w_i$ is the
weight of $v_i$, which may be positive or negative.
...
1
vote
0answers
52 views
Finding if an edge lies within a set of disjoint rectangles
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 ...
7
votes
0answers
145 views
Lower bound for the maximal vectors problem
I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, ...
21
votes
1answer
859 views
Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?
Consider the problem of finding a maximum disjoint set - a maximum set of non-overlapping geometric shapes, from a given collection of candidates. This is an NP-complete problem, but in many cases, ...
3
votes
1answer
150 views
Computing spanning trees with low crossing number using simplicial partitions
I'm reading a paper that uses the following result:
Let $S$ be a set of $n$ points in the plane. Then a spanning tree for $S$ with crossing number $O(\sqrt{n})$ can be computed in $O(n^{1+\epsilon})...
