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

267 questions
Filter by
Sorted by
Tagged with
201 views

### Hyperplanes not intersecting points on a cube

Consider the set of points in $\mathbb{R}^n$ with coordinates in $\{-1, 0, 1\}$. Find a hyperplane passing through the origin that contains no points in the set besides the origin. This is simple if ...
566 views

### Number of Maximum Overlap in n-Dimensions

Given a list of compact axis-aligned intervals (in 1-D), rectangles (in 2-D), cuboids (3-D) etc, what is the maximum number that overlap at any point? In 1-D there's a fairly simple solution that ...
391 views

I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$. $\text{increase}(a,b)$, which increases $t[a],t[a+1],... 1answer 128 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 (... 0answers 103 views ### Guarding paths variant of the Art Gallery Problem The optimization version of the traditional Art Gallery problem asks for a minimum set of point guards that can be placed within a polygon, such that any point in the polygon is visible from at least ... 1answer 340 views ### Adjacency-Preserving 2D Grid Embedding Consider a 2D grid, and a given planar graph$G$with$\Delta<4$(max node degree) and without odd cycles. What conditions should$G$satisfy so that when it is mapped (or embedded) into the 2D ... 1answer 184 views ### Delaunay tesselations and convex hulls According to Wikipedia the Delaunay tesselation in$d$dimensions can be viewed as a convex hull problem in$d+1$dimensions. Given a countable set of points$S\subset \mathbb{R}^d$and a point$p\in ...
Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the ...