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

learn more… | top users | synonyms (1)

4
votes
1answer
75 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 ...
0
votes
0answers
56 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 $$ ...
3
votes
0answers
39 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 ...
3
votes
3answers
82 views

Fast high-dimensional K-nearest neighbors

I'm aware of this question http://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
66 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 ...
4
votes
0answers
120 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
156 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
69 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
97 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
73 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
80 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 ...
6
votes
3answers
532 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
163 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
86 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
83 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
219 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
162 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} = ...
0
votes
0answers
102 views

Greiner-Hormann clipping with degeneracies

I'm trying to understand the paper "Clipping of Arbitrary Polygons with Degeneracies" by E. L Foster and J. R. Overfelt [1], which claims to extend the classic Greiner-Hormann polygon clipping ...
2
votes
0answers
36 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 ...
4
votes
1answer
102 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
85 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 ...
0
votes
0answers
115 views

Possibility of law enforcement with indistinguishable individuals?

Let $P$ be a set of individuals, suppose that each $p \in P$ has a specific footprint (e.g. SNPs or digital footprints) but that there may be indistinguishable individuals with the same footprint. ...
3
votes
0answers
163 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
97 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
95 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
74 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
47 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 ...
6
votes
0answers
110 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, ...
20
votes
1answer
323 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
133 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 ...
4
votes
0answers
89 views

Reduction from a geometric decision problem to its maximization problem

I am interested in the following NP-complete decision problem: ...
7
votes
2answers
262 views

Testing boolean vectors orthogonality with fast query-time

Consider the following problems, Problem1: INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$ TASK: preprocess INPUT in such a ...
8
votes
0answers
128 views

Approximating a convex polyhedron, with fewer inequalities

I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words, ...
4
votes
1answer
298 views

Computing the convex hull of lattice points

Consider a set of $n$ points in $\mathbb Z^2$. It is known that their convex hull can be computed in time $O(n\log n)$, or even $O(n\log h)$ where $h$ is the number of points in the convex hull. These ...
5
votes
0answers
79 views

Dynamic 2-dimensional orthogonal range reporting in external memory and linear space

Orthogonal 2-dimensional range reporting is the problem of storing a set of values from $U \times V$, where $U$ and $V$ are totally ordered universes, subject to queries of the form "Return all stored ...
3
votes
1answer
103 views

Efficient algorithm for computing equally distributed points in polytope?

Given a $d$-dimensional (rational) convex polytope $P$ with vertices $v_1, \ldots, v_n$, I would like to compute many equally distributed points that lie in $P$. "Equally distributed" is of course not ...
3
votes
1answer
112 views

Range searching: what is $\epsilon$?

I am interested in range searching purely as a black box in another problem. One problem in particular is that of shooting 2D rays among 2D segments. It seems that Agarwal and Matousek have a well ...
1
vote
0answers
44 views

Fixed orientation metrics

I am currently working on some computational geometry problems with non-euclidean metrics, and have some trouble on a fact that sounds easy enough, at least intuitively. The fact is as follows: ...
0
votes
0answers
43 views

Different estimators for uniform convergence of means/averages to expectations

In uniform converge results of means or averages to their expectations (think of the typical results involving VC-dimension, covering numbers, Pseudo-dimension, fat shattering dimension, ...) , the ...
2
votes
0answers
92 views

Geometry on a space of polynomial functions

I am considering some geometric concepts in a space of functions.But I am not sure the concept I consider is already defined in some references. Let $P_{1},...,P_{N}:\mathbb{F}_{2}^{n}\rightarrow ...
1
vote
1answer
115 views

Delaunay Triangulation of Parallelepiped

Given $n$ linearly independent vectors $v_1, v_2, \ldots, v_n$ in $n$-dimensional space. Let $V$ be the set of $2^n$ points of the form $x_1 v_1 + x_2v_2 + \ldots + x_nv_n$, in which $x_i$ can be $0$ ...
10
votes
1answer
255 views

Is it in NP to check if the convex hull contains the unit ball?

Given a set of $n$ points in $d$ dimensional Euclidean space, the problem is to determine if the convex hull contains the unit ball centered at the origin. Is this problem in NP? It is in co-NP ...
2
votes
0answers
97 views

Batch membership testing for convex polyhedron specified in vertex representation

I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the ...
9
votes
2answers
361 views

Select two numbers that sum to $p$, using sub-linear query time

Here is a nearest neighbor problem. Given reals $a_1, \ldots, a_n$ (very large $n$!), plus target real $p$, find $a_i$ and $a_j$ whose SUM is closest to $p$. We allow reasonable ...
12
votes
5answers
348 views

Motivation for volume estimation

What are some concrete and compelling applications for estimating the volume of convex polyhedra of the sort considered in the more recent papers on random walk methods? These papers on volume ...
2
votes
1answer
103 views

Bloom filter for predecessor queries?

Given a threshold $k$ is it possible to make a succinct data structure $S$ to answer queries of the form, given query $x$ does there exist a value $s$ in $S$ such that $s-k \leq x \leq s+k$? Like a ...
6
votes
0answers
122 views

VC dimension of Voronoi cells in R^d?

Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is ...
7
votes
1answer
223 views

Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?

Suppose I have some set of points in d-dimensional space, each with some mass. Our problem size will be the number of points in this set. After some roughly (within polylog factors) linear ...
2
votes
0answers
55 views

(eps,delta)-approx with VC-Dimension 1?

I have a domain $X$ and a set system $R$ on $X$, such that the sets in $R$ are one included in the other, that is, for any $A,B\in R$, either $A\subseteq B$ or $B\subseteq A$. The sets are not all ...
1
vote
1answer
83 views

Locating a set of 5 geometrically constrained points within a cloud of points

What is the most efficient way to find a set of 5 geometrically constrained, non-collinear points within a 3D point cloud of, for example, 100 points? All points are expressed with respect to a ...