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
0answers
108 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
153 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
68 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
91 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
67 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
76 views

Match two Polylines

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
162 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
218 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
160 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
92 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 ...
8
votes
0answers
82 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
114 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
161 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
96 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
305 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
125 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
294 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
111 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
113 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
252 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
96 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
358 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
345 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
120 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
214 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
82 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 ...
2
votes
0answers
80 views

Helly's number from biconvex functions [closed]

Helly's Theorem states the following. Suppose $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq ...
2
votes
0answers
139 views

Grouping a set of rectangles in larger rectangular regions

I have a set of rectangles, which I want to cluster (group) as shown here(I can not post images yet, so please bear with me). The approach I took was to consider central points of each rectangle as a ...
2
votes
1answer
425 views

Minimum shortest path cover of $n$ vertices in $R^m$

Informally, we define minimum shortest path cover to be the smallest number of shortest paths that cover all vertices of a graph. In other words, every vertex should belong to at least one of those ...
1
vote
0answers
67 views

Verifying the minimum degree of a geometric predicate

Let $F = (f_1, \ldots, f_n)$ be a sequence of multivariate polynomials $f_i : \mathbb{R}^d \to \mathbb{R}$, and $g : \{0,1\}^n \to \{0,1\}$ a boolean function. Say the composition ...
4
votes
1answer
141 views

Understanding the “gap theorem” in geometric spanners

I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition: Intuitively: A set of directed edges satisfies the gap property, if ...