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

263 questions
Filter by
Sorted by
Tagged with
1answer
98 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
229 views

0answers
104 views

### Reduction from a geometric decision problem to its maximization problem

I am interested in the following NP-complete decision problem: ...
2answers
329 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 ...
0answers
265 views

1answer
169 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 ...
0answers
92 views

### Intersection of N rectangles and M points

There are N rectangles parallel to X and Y axis and they do not overlap, also there are M points. For each point find an enclosing rectangle (or absence of one). Total runtime complexity should be not ...
1answer
287 views

### Minimum-area orthogonal rectangle coverage

Suppose there are N orthogonal rectangles on the planes, overlapping or not. I want to cover them with exact K orthogonal rectangles, overlapping or not. Each input rectangle must be completely ...
1answer
356 views

### Problem understanding “connectivity” characteristic for the $k$-connected subgraph problem

I am reading this article, and I am having trouble to understand the 11th definition (page 7) about the connectivity characteristic. I do understand the raw ...
1answer
202 views

1answer
126 views

### How to find the first $k$ points of high enough level using a priority search tree?

In reading Chan's paper, Closest Point Problems Simplified on a RAM, the following came up as a sub-problem: Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points (...