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

57 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
354 views

0answers
330 views

### NP complete problem help

I'm currently trying to find a reduction to this problem: Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
0answers
196 views

0answers
109 views

### Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D

This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes: Is there an algorithm that enumerates the ...
0answers
342 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 ...
0answers
114 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. ...
0answers
149 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, ...
0answers
487 views

### Examples of simple charging schemes

I am looking for a simple example of a charging scheme. That is, one that will take 1-2 minutes to explain in a talk. I know of one such example, though it concerns a geometric question, while I hope ...
0answers
451 views

### Cheapest dissection of a grid polygon into rectangles with cost

My problem: Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.) The rectangles must be taken from a predefined set (which ...
0answers
331 views

### Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?

Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate ...
0answers
293 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 ...
0answers
95 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 ...
0answers
284 views

### Voronoi partitioning on the 2nd and 3rd closest: how many pieces?

Where order-$k$ Voronoi diagrams partition according to the $k$ closest sites (de Berg et al. p. 169), consider partitioning on the 2nd and 3rd closest — call these [2,3]-Voronoi partitions. ...
0answers
370 views

### Strongly edge-guarding a 3d triangulation

Let $T$ be a planar triangulation. It is known that one can guard the faces of $T$ using at most $\lfloor n/3 \rfloor$ edge-guards (Worst-case-optimal algorithms for guarding planar graphs and ...
0answers
85 views

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
185 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 ...
0answers
456 views

### Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
0answers
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 ...
0answers
49 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 ...
0answers
99 views

0answers
467 views

### How to efficiently compute a bounding box of a 2D compact function support?

I've come to an interesting problem. Let's have a 2D scalar function F and make some assumptions on it: it has compact support (region where it is defined and non-zero) its support consists of at ...