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

Filter by
Sorted by
Tagged with
7
votes
2answers
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 ...
3
votes
2answers
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 ...
13
votes
2answers
391 views

Data structure for updates on intervals and querying number of zeros

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],...
3
votes
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 (...
4
votes
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 ...
4
votes
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 ...
1
vote
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 ...
4
votes
1answer
131 views

Balanced partitioning of a set of axis-parallel 2D rectangles

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 ...
11
votes
0answers
197 views

On preprocessing a convex polyhedron prior to sampling

Most of the algorithms for estimating the volume of a convex polyhedron $K \subset R^d$ assume the existence of an affine transform $T$ with the property that $$ B \subset TK \tilde{\subset}\ \...
6
votes
1answer
93 views

Number of distinct enclosing circles for N points

Several enclosing circles are possible for a given set of N 2D points. I am only talking about enclosing circles having 3 or more points on the circumference. What is the asymptotic limit of the ...
11
votes
2answers
1k views

Finding the closest pair between two sets of points on the hypercube

Given two subsets of the $d$-dimensional hypercube (i.e., $M, N \subseteq \{0,1\}^d$), I am looking for an algorithm which retrieves the points $m\in M, n\in N$ s.t. the hamming distance (or $L_1$-...
4
votes
1answer
145 views

Splitting line segments with a line

Given is a finite set $S$ of line segments in the plane. I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$. Here ...
2
votes
1answer
68 views

Covering only one of two types of objects in a cartesian space using minimum number of rectangles

There is a side problem in my research that I believe should be a known problem. I do not want to spend lots of time on a problem that already has been studied, but I do not have a name for the ...
1
vote
1answer
432 views

Algorithm for detecting closed region on a plane

First off, I just want to say that I am not well versed in computational geometry, so if this question has some obvious answer, I apologize. I tried googling it but I could not find anything. My ...
8
votes
1answer
298 views

Sampling from the Voronoi cell of a point

Fix a set of $n$ points $P \subset \mathbb{R}^d$. Now a query point $q$ arrives, and the goal is produce a point $r$ sampled uniformly at random from the Voronoi cell of $q$ in the set $P \cup \{q\...
4
votes
1answer
362 views

Finding the closest point to a sets of discrete points

In a paper I am reviewing, the authors define the following problem and construct an algorithm. They give no further references and I suspect it has appeared somewhere in the literature before. Let $...
14
votes
1answer
771 views

Computing the Löwner-John ellipsoid of a polyhedron

The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations ...
5
votes
0answers
301 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. ...
1
vote
1answer
148 views

Complexity of union (computational geometry)

I'm courrently rading "Computational Geometry" from Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars and found the following theorem 13.9. Let $S$ be a collection of convex polygonal ...
6
votes
1answer
101 views

Hidden constant in eps-sample size computation

Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $ O\left(\frac{1}{\varepsilon^2}\left(d+\log\frac{1}{\...
8
votes
3answers
6k views

VC dimension of polynomials (in one variable) of degree d

Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$. I am searching for ideas that can prove the ...
5
votes
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 ...
4
votes
0answers
175 views

Approximation ratio for covering n points in d dimensions

What is best known approximation ratio for the following problem : Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a ...
10
votes
1answer
156 views

Longest edge length of the greedy spanner on uniformly distributed pointsets in $[0,1]^d$

Let $P$ be a set of $N$ points in $\mathbb{R}^d$. For any $t \geq 1$, a $t$-spanner is an undirected graph $G=(P, E)$ weighted under the Euclidian measure, such that for any two points $v$, $u$, the ...
2
votes
2answers
169 views

Maximum Crossing number of topological graph

The crossing number of a graph $G$ is defined as the least number of crossings introduced when $G$ is drawn as a topological graph in the plane. Is there anything known about the maximum number of ...
1
vote
0answers
128 views

Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D [closed]

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
0
votes
0answers
479 views

Identify all of the non-overlapping rectangular regions of a simple concave polygon

I am looking for an algorithm to identify all of the rectangles bounded by two parallel edges of a polygon. The rectangle must remain inside of the polygon at all times. My polygon is simple and will ...
0
votes
0answers
504 views

Get Largest Inscribed Rectangle of a Concave Polygon

I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon. In other words, I want to ...
12
votes
2answers
2k views

Cover a Concave Polygon with a minimum number of rectangles

I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle. I thought about ...
7
votes
2answers
196 views

Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions

Consider a planar subdivision, with F faces, V vertices, E edges, and I face-vertex incidences. For simplicity, assume a "non-degenerate" situation in which each vertex occurs on the boundary cycle of ...
3
votes
3answers
455 views

Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
6
votes
0answers
540 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 ...
15
votes
1answer
364 views

Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
1
vote
1answer
882 views

Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?

An elaboration on this question, but with more constraints. The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions. The bucketing grid seems to work ...
2
votes
0answers
76 views

Connectivity keeping centralized algorithm for multi-agent network navigation

We have a network of $N$ agents moving in a field. Every agent has communication bandwidth of range $R$. During the process we must keep all-to-all communication among the agents. So we have ...
9
votes
1answer
465 views

Algorithm for approximating convex bodies by a convex hull of ellipsoids

I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body $K$ by the convex hull of $...
5
votes
1answer
4k views

An algorithm to efficiently draw a extremely large graph in real time

Are there any algorithms to draw a billion node graph or to aggregate the information? The idea would be to allow for it to be parallelized using map reduce so it could be done in realtime I was ...
9
votes
1answer
417 views

Is there a suitable algorithm to draw a mixed constituency/dependency graph in a coordinate system?

I am looking for an algorithm to draw a mixed constituency/dependency graph (for a linguistic application). Such a graph would have two different types of vertices (tokens, nodes), and two different ...
7
votes
1answer
262 views

Placing points far away from each other in simple polygon

I am sure the following problem has been studied before, but I did not find any literature about it. ...
5
votes
1answer
204 views

Finding a simple dual of a simple graph in some surface

Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph ...
11
votes
1answer
811 views

Finding a dual of a graph

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ ...
13
votes
2answers
496 views

Learning triangles in the plane

I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ ...
22
votes
2answers
2k views

Detecting two kinds of almost-simple polygons

I'm interested in the complexity of deciding whether a given non-simple polygon is almost simple, in either of two different formal senses: weakly simple or non-self-crossing. Since these terms are ...
15
votes
1answer
519 views

Drawing graphs with few "sharp" vertices?

For a planar embedding of a planar graph on a plane with straight edges, define a vertex as a sharp vertex if the maximum angle between two consecutive edges around it is more than 180. Or in other ...
4
votes
1answer
137 views

Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices

Suppose we have a multigraph with vertex set $V$ where for each $v \in V$, $d_v > 0$ is the diameter of the vertex. We want to put a linear ordering on the set of vertices such it minimizes ($L_1$ ...
9
votes
1answer
226 views

Counting the number of thick regions which overlap a square

Let $S$ be a unit square. As a function of $\beta$, what is the maximum number of $\beta$-fat pairwise-disjoint regions with diameter at least 1 which can intersect $S$? Below, we give a figure ...
9
votes
2answers
1k views

Polygon within polygon generalization problem

I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical ...
9
votes
2answers
4k views

VC-dimension of spheres in 3 dimension

I am searching for the VC-dimension of the following set system. Universe $U=\{p_1,p_2,\ldots,p_m\}$ such that $U\subseteq \mathbb{R}^3$. In the set system $\mathcal{R}$ each set $S\in \mathcal{R}$ ...
8
votes
2answers
1k views

Dynamic Upper Envelope of lines in the plane

There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey Davenport-Schinzel sequences and their geometric applications. ...
4
votes
0answers
209 views

Triangulation with maximum greatest area

Given a point set $P$ and a triangulation $T$ of $P$ with $d$ triangles, let's define $$\alpha(T) = (\alpha_1, \alpha_2, \ldots, \alpha_{3d})$$ which denotes the series of interior angles of $T$, ...