# 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).

251 questions
Filter by
Sorted by
Tagged with
1answer
77 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 ...
1answer
172 views

### Proof for Upper Bound of Sum of Square Roots Problem

In , Garey et al. identify what would later be known as the Sum of Square Roots Problem in the course of working out the NP-completeness of Euclidean TSP. Given integers $a_1, a_2, \ldots, a_n$ ...
0answers
61 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 ...
0answers
73 views

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$...
3answers
177 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 ...
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$...
0answers
164 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 ...
1answer
390 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 ...
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 ...
1answer
179 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 ...
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 ...
1answer
187 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 ...
3answers
568 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 ...
0answers
246 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 ...
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 ...
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 ...
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 ...
1answer
196 views