# 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
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 ...
332 views

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 ...
183 views

947 views

### Graph layout algorithm

I have an undirected graph on matris by vertex adjacency relations like that; ...
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 ...