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

259 questions
Filter by
Sorted by
Tagged with
42 views

### VC-dimension of infinite set of triangle wave

I am searching for the VC-dimension of the following: What is the VC-dimension of the infinite set of triangle wave functions with amplitude 1 and period parameter p on points on the line? 2πarcsin⁡(...
51 views

### VC-dimension of a ball [closed]

I am searching for the VC-dimension of the following: What is the VC-dimension That can ball (3D) can shatter in 3 dimension?
50 views

### How hard is deciding the existence of a polygonization with prescribed perimeter?

Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or ...
124 views

### Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?

I need to use the following well-known result in my paper: Let $X$ be a set of $n$ points in $\mathbb{R}^d$. Then $(X,\ell_2^d)$ embeds isometrically in $\ell_p^\binom{n}{2}$ for all $p \geq 1$. ...
81 views

155 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 ...
62 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 ...
40 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 ...
509 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 ...
335 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 (...
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 \... 1answer 300 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 ... 0answers 140 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\}-... 1answer 226 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 ... 1answer 149 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 ... 1answer 331 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 ... 0answers 170 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 ... 1answer 313 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 ... 0answers 80 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? ... 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\... 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 ... 1answer 66 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 ... 1answer 79 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 ... 1answer 2k views ### VC-dimension of triangles in 2D space [closed] I have been reading in multiple places (e.g. , 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 ... 1answer 294 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") ... 1answer 161 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 ... 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  $... 0answers 89 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$... 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 ... 0answers 100 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 169 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 538 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 102 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 207 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 116 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 339 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 578 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 284 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 115 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 96 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 227 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 222 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} = \{...
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/...