Questions tagged [computational-geometry]

Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.

Filter by
Sorted by
Tagged with
11
votes
1answer
9k views

How do I construct a doubly connected edge list given a set of line segments?

For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i \...
10
votes
4answers
794 views

Recovering a point embedding from a graph with edges weighted by point distance

Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the ...
5
votes
1answer
679 views

What are some interesting applications of the skyline problem?

You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each ...
2
votes
2answers
2k views

Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
2
votes
1answer
793 views

How to find vertices of bounded region made by intersection of lines

Suppose we have random lines made with 2 points. and point has (x,y) For example: Now when we draw a random line you will see many lines intersect with each other. This eventually gives rise to ...
12
votes
2answers
2k views

Tiling an orthogonal polygon with squares

Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon. I found several references ...
11
votes
2answers
4k views

Closest pair of points between two sets, in 2D

I have two sets $S,T$ of points in the 2-dimensional plane. I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as ...
5
votes
1answer
712 views

What is the minimum square partition of an almost-square rectangle?

This question is motivated by an older question about tiling an orthogonal polygon with squares. It is a generalisation of my former question about how to prove that the minimum square partition of a ...
3
votes
1answer
231 views

How to prove that the minimum square partition of a 3X2 rectangle has 3 squares

This question is motivated by an older question about tiling an orthogonal polygon with squares.         Given a $3\times 2$ rectangle like the first image, the ...
19
votes
3answers
8k views

Line separates two sets of points

If there is a way to identify if two sets of points can be separated by a line? We have two sets of points $A$ and $B$ if there is a line that separates $A$ and $B$ such that all points of $A$ and ...
7
votes
2answers
2k views

$O(n \log n)$ algorithm for disjoint segment visibility problem

Consider we have $n$ disjoint segments and a point $P$ which is not on any segment. I want to find an $O(n \log n)$ algorithm to check which segments are visible from $P$. A segment is visible from $P$...
6
votes
1answer
599 views

How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats). I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= v[i]...
2
votes
2answers
118 views

Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line

I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only ...
20
votes
2answers
2k views

How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?

I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the ...
7
votes
3answers
2k views

If a point is a vertex of convex hull

The exercise is Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex of convex polygon formed from points of $S$. The problem is I am a little bit confused with ...
3
votes
2answers
790 views

Data structure for adjacent rectangles

I have a file with a list of non-overlapping rectangles covering the entire space (they are adjacent). I would like to plot efficiently the graph edges that connect each rectangle center point with ...
19
votes
3answers
428 views

How many cookies in the cookie box? — Tiling stars

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
5
votes
2answers
346 views

How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The ...
3
votes
1answer
97 views

High-dimensional geometry and P vs. NP

Background: Recently, I obtained the following equivalent problem to SAT. We are given as input a CNF formula with $n$ variables and $m$ clauses. Suppose we have an $n$-dimensional hyper-cube centered ...
19
votes
3answers
3k views

Maximum Enclosing Circle of a Given Radius

I try to find an approach to the following problem: Given the set of point $S$ and radius $r$, find the center point of circle, such that the circle contains the maximum number of points from the ...
11
votes
2answers
2k views

How do I test if a polygon is monotone with respect to a line?

It's well known that monotone polygons play a crucial role in polygon triangulation. Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line ...
3
votes
1answer
160 views

Solving a variant of the Exact cover problem

I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover). Now, it ...
2
votes
2answers
3k views

detect closed shapes formed by points

I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the ...
1
vote
2answers
653 views

Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the ...
16
votes
1answer
3k views

How do I test if a polygon is monotone with respect to an arbitrary line?

Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice. Given a polygon $P$, is it possible to ...
9
votes
1answer
6k views

Rectangle Coverage by Sweep Line

I am given an exercise unfortunately I didn't succeed by myself. There is a set of rectangles $R_{1}..R_{n}$ and a rectangle $R_{0}$. Using plane sweeping algorithm determine if $R_{0}$ is ...
7
votes
1answer
3k views

Lower bound for Convex hull

By making use of the fact that sorting $n$ numbers requires $\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $...
7
votes
4answers
298 views

Detecting coplanarity by given pairwise distances

Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints. Note that we'...
7
votes
1answer
10k views

Checking Feasibility of Linear Program in Polynomial Time

Given a linear system of the form: $$\begin{array}{c} x_r = a \quad x_j = b \\ c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\ x_1+x_2 + x_3 + \ldots + x_n = k\\ 0 \le a,b,x_1,x_2,x_3...x_n \le 1\\ k \ge 0 \...
5
votes
2answers
9k views

Determine whether a point lies in a convex hull of points in O(logn)

I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one ...
4
votes
2answers
1k views

Finding least number of line segments with length $L$ that cover $N$ points

The problem is defined as: Given $N$ points on an infinite line, find the least number of line segments of length $L$ that cover all points (including endpoints) after changing one point. That ...
4
votes
1answer
726 views

Efficient algorithm to compute the minimum of multiple piecewise linear functions

Let $f_i(x)$ be a continuous, convex, piecewise-linear function for $i=1,\ldots,n$. Define $$g(x) = \min_{1\leq i\leq n} f_i(x).$$ Clearly, $g(x)$ is also a piecewise linear function. What would be ...
3
votes
1answer
269 views

Number of double wedges containing a point

We have a set of $n$ double wedges on a plane. (By double wedge, I mean two lines intersecting at a point, with opposite sides of the point considered as "inside" the double wedge.) Now ...
3
votes
1answer
672 views

Creating a 2D map of objects given a sparse matrix of pairwise distances

I have a set of points on the two-dimensional plane, but their locations are not given to me. I am given the distance between some pairs of the points. However, I only know these differences for ...
3
votes
2answers
4k views

Efficient algorithm for finding maximum subset of intersecting rectangles

What is an $O(n \log n)$ algorithm to find how big the largest subset of $n$ axis-aligned rectangles (in the plane) that contain a common point is? Perhaps by reducing this to a problem with such ...
2
votes
1answer
329 views

Algorithm for nearest edge detection with respect to a point (in all directions)

I'm looking for an algorithm, a set of algorithms, or any pointers/remarks how to solve the following problem: Given a polygon, a central point, and a set of points scaterred around the central point ...
2
votes
2answers
2k views

Minimizing the maximum Manhattan distance

Given N points on a grid, find the number of points, such that the smallest maximal Manhattan distance from these points to any point on the grid is minimized. Also, determine the distance itself. ...
1
vote
2answers
468 views

criterion for two line segments intersecting

I have two line segments $[(x_1, y_1),(x_2, y_2)] $ and $[(x_3, y_3),(x_4, y_4)] $ and I want to know if they intersect. My current algorithm tries the following: the line $[(x_1, y_1),(x_2, y_2)] $ ...
1
vote
1answer
1k views

A plane-sweep algorithm for a points in triangles inclusion problem

I was given the following homework assignment: Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle ...
8
votes
1answer
427 views

Circles covering a rectangular, how to verify it?

This may be basic to some of you, but excuse my inexperience with comp. geometry: Given a set of $n$ circles with centers $(x_i, y_i)$ for $1 \leq i \leq n$ and each having radii $r$. Also given a ...
7
votes
1answer
405 views

Given 2 sets of n points: minimize sum of traveled distances

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
6
votes
1answer
2k views

Find the point with minimum max distance to any point in a set

Say I have a set of points on a 2d plane, how do I find the point(s) where the maximum euclidian distance to any of the points in the set is minimized?
5
votes
1answer
106 views

Delaunay Triangulation on Convex Polytopes — Uniform Sampling

My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts: ...
5
votes
1answer
321 views

King of the North: Placing bannermen surrounding castle

I was trying to solve the King of the North problem in Kattis. Basically, the problem is, the king has a castle to protect. To do this, he wants to place bannermen across the open areas surrounding ...
4
votes
2answers
1k views

A heuristic for finding a maximum disjoint set

Background I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares. This problem is NP-complete. Many papers suggest approximation ...
4
votes
2answers
2k views

Why are the two farthest points vertices of the Convex Hull?

I read that in a 2D space, the two points farthest away must be in the convex hull (CH). Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point ...
3
votes
2answers
109 views

Finding closest edge to a point in a planar graph

I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a <...
3
votes
0answers
43 views

Find the largest interior rectangle composed of partitioning rectangles

Suppose a rectangle $R$ is partitioned into more than one smaller rectangles of positive area. What is the fastest algorithm to find the largest rectangle strictly within the all-enclosing rectangle $...
3
votes
0answers
71 views

Computing the line equations of two crossing tangents in a point set separated by a vertical line?

I have provided a picture as an example. We have two point sets, P and Q. P is to the left of this vertical line (named x = x0), and Q is to the right of it. The goal is to compute the line equations ...
3
votes
2answers
247 views

Find all neighbors at a certain distance, in 3 dimensions

I have two algorithms which I would like to implement: First, given a (very long) list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d>0$, ...