Questions tagged [computational-geometry]
Questions about algorithmic solutions of geometric problems, or other algorithms making usage of geometry.
863
questions
2
votes
0
answers
44
views
Optimal way to survey a road
There is a road (a planar curve) of length 1. A treasure is placed in a random spot on the road. The treasure location is a uniform random variable, so that the probability to find the treasure in an ...
- 5,994
5
votes
1
answer
81
views
How to detect intersecting segments based on length of the segments
As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or ...
- 153
4
votes
1
answer
489
views
Point in Polygon Problem: Has anybody invoked the line integral?
Some twenty years prior I was given the task to solve the Point in Polygon problem for a piece of commercial software. I solved it invoking the ray casting algorithm. After a variety of enhancements ...
- 49
5
votes
1
answer
599
views
Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part
I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X_i,1\leq i\leq m$. I would like to use a ...
- 53
7
votes
2
answers
3k
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$...
- 73
4
votes
1
answer
626
views
perspective transformation of a grid
A perspective transformation of a point is defined as follows:
$ x' = \frac{M_{11}x + M_{12}y +M_{13}}{M_{31}x + M_{32}y +M_{33}} $
$ y' = \frac{M_{21}x + M_{22}y +M_{23}}{M_{31}x + M_{32}y +M_{33}} ...
- 143
2
votes
2
answers
309
views
How to find the original coordinates of a point inside an irregular rectangle?
I'm a third year computer science student. I'm working on a project Data-show touch screen In schools classrooms.
I'll try to explain my problem as much as I can.
...
- 123
4
votes
1
answer
952
views
How to handle horizontal lines in the Polyfill Algorithm?
When I look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle horizontal lines. Does anyone have any idea how horizontal lines should be handled?
For ...
- 141
6
votes
1
answer
625
views
Voronoi cells for rectangles
I am looking for a reference on the following variant of a Voronoi diagram:
Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint.
Instead of Euclidean ...
- 5,994
0
votes
0
answers
310
views
Bentley–Ottmann algorithm time complexity issue
In the Bentley–Ottmann algorithm, Regarding :
Find the segments r and t that are immediately below and above s in T
(if they exist) and if their crossing forms a potential future event
in the ...
- 355
6
votes
1
answer
639
views
Finding a way out of a polygon
There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$:
The goal is to select one of the polygons, say $D_i$, and attach to it ...
- 5,994
3
votes
1
answer
2k
views
Finding a maximal set of nonintersecting line segments in a unit circle
Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning ...
- 385
5
votes
0
answers
116
views
3D mesh segmentation simple algorithm
I am developing the algorithm reported in this article:
Lest square conformal mapping
Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the ...
- 51
9
votes
1
answer
4k
views
Sort a list of points to form a non-self-intersecting polygon
Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \...
- 301
1
vote
0
answers
342
views
Moving a set of points in the plane subject to constraints
I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum.
Let $X$ denote the disjoint union of $n$ one-point sets. Let $f:X\...
- 111
4
votes
1
answer
3k
views
Find set of non-overlapping rectangles in a 2D grid
I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned ...
D.W.♦
- 159k
8
votes
1
answer
2k
views
Computing farthest pair of points in d dimensions
Question: Given $n$ points in metric space, find a pair of points with the largest distance between them.
If we restrict ourselves to $d$-dimensional Euclidean space then, a naive algorithm of ...
- 338
4
votes
4
answers
3k
views
How can I sum pixel values over a rotated rectangle?
I have an optimization problem in which I need to sum pixel values in an image over a rectangular region. This is a core component of the optimization so it will be done often and the naive solution ...
- 197
4
votes
1
answer
1k
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 ...
- 143
7
votes
3
answers
1k
views
Partial polygon matching
I am looking for fast procedures for polygon matching, i.e. checking polygon similarity under different transforms
translation only,
translation + rotation,
translation + scaling,
translation + ...
user16034
1
vote
1
answer
116
views
maximum distance in between points in taxicab metrics - inserting and deleting points
Let's define distance (taxicab metrics) between two points $(x_1, y_1)$ and $(x_2, y_2)$ as
$$|x_2-x_1| + |y_2-y_1|$$
Initially, there are given empty set of points.
I think how to find maximum ...
- 573
1
vote
1
answer
171
views
Finding first/last intersection in a set of lines
I am given $n$ lines, in the form $y=ax+b$, where
there are no two lines with the same $a$
no three lines intersect in the same point
no vertical lines
I need to find in time $O(n\log n)$ an $x'$ ...
- 355
5
votes
1
answer
434
views
Constrained Smallest Enclosing Ball Problem
Let $X = \{x_1, x_2, ..., x_n\} \subset \mathbb{R}^m$ be a finite set of points. Smallest enclosing ball is a well-known problem that asks for the $m$-ball that covers all $x_i \in X$, while having ...
- 175
3
votes
1
answer
153
views
Enumerate all pairs, in order of increasing distance, efficiently
Given $n$ points in 2D, e.g., $p_1,p_2,....,p_n$, there are $n^2$ possible pairs of points. I want to output the list of $n^2$ pairs, but sorted according to their distance (e.g., the pair of two ...
- 51
1
vote
1
answer
846
views
Polygon casting - Removing from mold by rotation
The following question appears in Section 4.9 of "Computational Geometry: Algorithms and Applications" By Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf:
Show that the ...
- 135
2
votes
1
answer
387
views
Shortest continuous path between shapes without passing thru other shapes, in a specific order?
I have the following points, shapes, and paths. I would like to find a path that goes through all of them:
I want a path that first traverses the circle, then traverses the square, then traverses ...
- 121
7
votes
2
answers
953
views
Efficient algorithm for rectangle containment
Given a set of $n$ intervals on a line, there is a $O(n \log n)$ algorithm to find intervals which are contained in other intervals (e.g., Manber, "Using induction to design algorithms", 1988). Is ...
- 171
2
votes
1
answer
30
views
Are there any articles or software which can infer original shapes from overlapping shapes?
Given that some shapes overlap in an image, are there any papers or articles or code which can infer the original shapes from the overlapping?
I am thinking to apply some machine learning to this ...
- 143
31
votes
0
answers
813
views
Largest set of cocircular points
Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior).
This can be done in $O(n^3)$ ...
- 441
7
votes
1
answer
461
views
Given a moving ball in a grid, which squares does the ball reach?
You are given an m x n grid. A dimensionless ball is placed at the centre of one of the grid squares and starts moving in one of 4 directions: north-east, north-west, south-east, or south-west. The ...
- 158
3
votes
2
answers
177
views
Plow a 2D polygonal area
I have a problem that is similar to this that I am trying to solve:
"Given a randomly-shaped field, what is the best (fastest I guess) way to plow it? Every part of the field must be plowed, plowing ...
- 161
2
votes
0
answers
77
views
Determining whether a line between two points in a monotone polygon is a valid diagonal
Given a monotone polygon, with it's vertices given in counter-clockwise orientation, is there any fast process to determine whether the line between two vertices of that polygon ...
- 121
1
vote
0
answers
63
views
Solving a recurrence relation [closed]
I am having problem with solving the following recurrence relation. $A$ is a set, there are at most $k+1$ of this set and $|A|$ is at most $n/2$.
$T(n) = O(n log k) + \sum_A T(|A|)$
I guess it can't ...
- 1,529
4
votes
1
answer
1k
views
Cover points with minimal number of spheres of fixed radius
I have a set of k n-dimensional points:
P1(x11, x12, ..., x1n), P2(x21, x22, ..., x2n), ..., Pk(xk1, xk2, ..., xkn).
A distance D(Pa, Pb) is defined between any two points, which satisfy usual ...
xaxa
7
votes
3
answers
4k
views
Find k nearest neighbors on a sphere
Given a set $S$ of $N$ points on a sphere, and another point $P$ on the sphere, I want to find the $k$ points in $S$ that are the closest (Euclidean or great circle distance).
I'm willing to do a ...
- 173
3
votes
0
answers
62
views
Is this sparsity constrained convex projection problem NP-hard?
Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$ and an ...
- 1,721
10
votes
2
answers
224
views
Complexity for finding a ball that maximizes the number of points lying in it
Given a set of points $x_1, \ldots, x_n \in \mathbb{R}^2$ and a radius $r$. Which is the complexity of finding the point with higher number of points at a distance smaller than $r$. E.g the one that ...
- 223
3
votes
2
answers
354
views
Determine the move in which a LOGO turtle crosses a point that it has already visited
I was given the following problem in an test (at codility.com)
A turtle starts at (0, 0) on a cartesian graph. We have a non-empty
zero-indexed "moves" list that contains positive integer numbers....
- 171
3
votes
1
answer
1k
views
Understanding Closest Pair Algorithm (CLRS)
I'm reading CLRS Section 33.4 Finding the closest pair of points. At exercise
33.4-2 they say
33.4-2
Show that it ...
- 749
1
vote
1
answer
135
views
Given a set of irregular polygons finding a set of vertices (one on each polygon) such that distance between points is maximized
Given a set of irregular polygons with the same number of points, where $polygon_i$ is completely contained within the boundary of $polygon_{(i+1)} $.
I need to find a set of vertices (one vertex ...
- 13
2
votes
1
answer
167
views
Convex Hull in no particular order
The proof for the $\Omega(n\log n)$ lower bound for calculating the convex hull by using order-type predicates that I have come across uses the fact that if there was possible to calculate the convex ...
- 133
4
votes
1
answer
500
views
Find the shortest OPEN path connecting a set of 2D points (special case)
I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered.
The ...
- 143
1
vote
3
answers
862
views
Given a path of 2d points and a maximum distance, find the minimum number of line segments needed to "connect" all points
I have an array of 2 dimensional points describing a path. I want to reduce the number of points needed to describe this path by using line segments that connect multiple points on the same line, ...
- 133
1
vote
0
answers
34
views
How to find an axis-aligned hyper box whose set of integer points minimizes Jaccard distance to a given finite set of points $X \in {\mathbb Z}^d$?
So I saw this question posed on math.se for $d=3$. Suppose we are given a finite set $X \subset {\mathbb Z}^d$ of $n$ points. The goal is to find a hyper box of integer points $ B = [k_{1,1},k_{1,2}] \...
- 1,721
1
vote
0
answers
33
views
Inherent complexity of testing line segment intersections with aligned and oriented bounding boxes?
It is well known that in practice, a substantial difference in run-time between algorithms for testing intersection of a line segment with aligned or oriented bounding boxes (in computer graphics ...
- 121
0
votes
1
answer
190
views
Algorithm for projection of polytope
Let a convex bounded polytope be given by an intersection of half planes: $Ax \leq b$. Let $z=Cx$ be a vector (in my case $z$ is 2-dimensional, while $x$ has a higher dimension). How can I compute $D$...
- 101
9
votes
2
answers
398
views
Find the central point in a metric-space point set, in less than $O(n^2)$?
I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I ...
3
votes
1
answer
147
views
Covering a polygon with n circular rings
Question 1: Why we can/can't solve the following problem using a geometric constraint solver?
Question 2: Is there any algorithm to solve this problem?
Question 3: Can we reduce this problem into some ...
- 87
3
votes
3
answers
880
views
What are algorithms for computing contours from given edges?
Let's say I have a set of edges which makes the contour, however there are too many of them and some are too long. I have to remove edges, and shorten them to make contour. I cannot add new edges!
I ...
- 228
2
votes
1
answer
4k
views
Getting the essential from the fundamental matrix
Is it possible to get E from F? I suppose that can't work, because then I could calculate the the extrinsic (and maybe also intrinsic?) parameters of the cameras without a calibration object of known ...
- 279