Questions tagged [computational-geometry]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
125 views

Weighted $l_1$ distance

So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along ...
2
votes
1answer
329 views

maximizing inner product

Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each, how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \...
5
votes
0answers
73 views

Finding of dimension of algebraic varieties

I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf). Are ...
0
votes
1answer
140 views

Lowerbound for the minimum distance between points in a “nice” triangulation

Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. ...
4
votes
0answers
209 views

Voronoi diagram in presence of polygonal obstacle

Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$. The distance between a point $p \in ...
5
votes
2answers
211 views

Voronoi Diagram of Lines

Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(...
2
votes
0answers
543 views

Shortest non-crossing geometric paths

I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so ...
1
vote
0answers
38 views

Current review on polygon partition problems

Mark Keil(1) provides an extensive survey of polygon partitioning and polygon covering alrogithms. This survey was written in 2000. Is there a more recent survey on this topic?
2
votes
0answers
195 views

Inclusion of polytopes

Consider the following two system of linear (in)eqaulities: $S = Ax \leq b;\; Cx = e$ $T = Dx \leq d;\; Gx = g$ How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
3
votes
0answers
107 views

Equivalence of weighted Minkowski sums

Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices. Furthermore, consider a variant of the Minkowski sum (somehow ...
3
votes
0answers
76 views

Triangular range counting query in poly-logarithmic time

What is the minimal space requirement for triangular range counting queries in plane if one wants to process each query in poly-logarithmic time? In [Goswami et al, 2004] they preprocess the ...
2
votes
0answers
71 views

Check whether a point is a vertex of Minkowski sum of polytopes

Given $n$ polytopes $$\begin{align*} P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\ P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...
2
votes
0answers
53 views

How to compute the basis

Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and $W= \begin{...
1
vote
0answers
74 views

Compute basis of vertex set of polytope

I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope. Formally, INPUT: a polytope $$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\...
3
votes
1answer
312 views

Does Approx Carathéodory's theorem implies dimensionality reduction

Carathéodory's theorem says that if a point $x$ of $R^d$ lies in the convex hull of a point set $P$, then there is a subset $P′ \subseteq P$ consisting of $d + 1$ or fewer points such that $x$ can be ...
2
votes
0answers
212 views

Convex hull of polytopes

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,......
4
votes
1answer
114 views

Polytopes convex hull

Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I ...
3
votes
2answers
190 views

Is this covering problem NP-hard?

Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ ...
2
votes
1answer
205 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
2
votes
0answers
39 views

centralized deterministic Spanner construction with low degree and low stretch

Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
11
votes
1answer
248 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
110 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
votes
1answer
286 views

Vertices of a polytope

Consider the polytope $P=\{(x_1,x_2,...,x_n)\in \mathbb{R}^n| \sum_{i=1}^n x_i=1; 0\leq a_i\leq x_i\leq b_i, i=1,...,n\}$ where $a_i$ and $b_i$ are constant lower and upper bounds for $x_i$. Is it ...
2
votes
2answers
337 views

Coreset and VC dimension

I am trying to understand the notion of $\epsilon$-coreset and its relation with sampling bounds of a range space having a finite VC-dimension. Although both of them give an $\epsilon$-approximation ...
2
votes
1answer
74 views

Complexity for single-linkage clustering with max norm

Let $S\in\mathbb Z^d$ be a set of points, with some notion of distance $d(x,y)$ between two points $x,y\in S$. I am specifically interested in the max distance, that is $d(x,y)=\max_{1\le i\le d} |x_i-...
0
votes
1answer
69 views

Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane

Question summary: what are the known efficient algorithms to find the intersections of 1-dimensional curves living on a 2-dimensional plane? Detail: I have a set of 1-dimensional curves on a 2-...
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 ...
10
votes
1answer
157 views

Largest cell in an arrangement

Q. What is the complexity of finding the largest volume bounded cell in an arrangment of $n$ hyperplanes in dimension $d$? I feel I should know this... But I am not finding a definitive reference. ...
6
votes
1answer
121 views

Maximum number of geometrically disjoint paths - is the complexity known?

Let $G$ be an undirected graph, given with a planar drawing. We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct ...
3
votes
1answer
56 views

Emptiness of complement of subspace arrangement

Given $k$ affine subspaces in $\{0,1\}^n$, consider the problem of testing whether their union covers all of $\{0,1\}^n$. What's the complexity of this problem? P.S.: It seems that this can be ...
3
votes
1answer
132 views

Generalization of Beck's theorem

Beck's theorem is a classical result in discrete geometry which describes about the geometry of points in the plane. The result states that a finite collections of points in the plane fall into one of ...
5
votes
2answers
208 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 ...
1
vote
0answers
28 views

Extending Delaunay graphs in d-space

I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space. ...
2
votes
1answer
123 views

Weighted furthest point voronoi diagrams

I found that Weighted nearest neighbor voronoi diagrams are widely studied and there are optimal algorithms for that. But I could not find anything on Weighted furthest point voronoi diagrams !! But ...
11
votes
1answer
303 views

Implementation of partition trees?

Have partition trees ever been implemented? Here, I'm talking about the partition trees from computational geometry. The earliest (near-)optimal versions of which were due to Matousek and others, ...
2
votes
1answer
99 views

Approximating the value of k in $k$-mean clustering problem

Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by ...
1
vote
1answer
60 views

Finding a point outside of each of a set of polygons in a bounded space

I know there are algorithms for finding a point inside a simple polygon. Given a set of polygons inside a rectangle (think a bunch of polygons on a computer screen), is there an efficient algorithm ...
0
votes
0answers
211 views

Clustering in sublinear time/query

Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy: 1) Minimizing the number of balls that are required to cover all ...
0
votes
2answers
159 views

A continuous center point of a convex spherical polygon

In discrete geometry, the center point $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a center point ...
10
votes
1answer
136 views

Minimum equidecomposable decomposition

Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all $i$...
0
votes
1answer
668 views

maximum weighted 2D coverage problem by a rectangle

Let $P=\{p_1,\ldots,p_n\}$ be a set of $n$ points in a 2D plane, that is $p_i\in \mathbb{R}^2$, $\forall i=1,\ldots,n$. Each point, $p_i$, is associated with a weight, $w_i \geq 0$. Imagine a axis-...
6
votes
2answers
497 views

Would a purely topological computational model be useful in decision problems in topology?

If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the ...
0
votes
1answer
80 views

Algorithms to classify the geometrical relationship of two 3D-geometries

I have multiple 3D volumes which are represented by their boundaries (set of polygons each represented as a list of 3D-coordinates). I am now looking for algorithms to decide if volume A is inside ...
5
votes
3answers
209 views

Locating a point inside a union of simple polygons

I have a set of polygons (convex, concave – non-convex, not self-intersecting) in a plane. There may be intersections between polygons. Polygon is defined by points (cartesian coordinate system). ...
2
votes
0answers
186 views

Eulerian Triangulations

Hi i am looking for algorithms to decide whether a planar pointset has a eulerian triangulation i.e. a triangulation that makes every vertex of even degree. I cam across this page http://cs.anu.edu....
2
votes
0answers
106 views

Worst-case optimal Delaunay algorithm based on spatial sort and walking?

Buchin [2] showed that under "reasonable" assumptions, (polynomial point spread) incremental construction of Delaunay triangulations using the biased randomized ordering of Amenta et al. [1] with a ...
0
votes
0answers
422 views

Rectangular constraints in Delaunay Triangulation without edges within

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 ...
0
votes
1answer
68 views

Define metric for systems of set of points

Given a set of points $p_1, p_2, ..., p_n$ and a collection of sets from $n$ points $S_1, S_2,...,S_m$. The pairwise distance between any three points $(p_1, p_2, p_3)$ satisfies triangle inequality $...
3
votes
3answers
384 views

Partitioning a set of 2d polygons into intersection-connected subsets

My question is given a set of 2d polygons how can I find the connected components of polygons according to a criteria based on intersection or proximity of them. In other words I have a set of ...
3
votes
1answer
152 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 ...