Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

2
votes
1answer
73 views
+50

Finding pairs of points that have a given offset

Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points ...
1
vote
2answers
76 views

3-SUM hardness vs lower bounds on the complexity

I've recently encountered a new (for me) notion from computational complexity theory called 3-SUM hardness which is based on the conjecture that 3-SUM problem can not be solved in ...
0
votes
0answers
38 views

Find cell neighbors of a given edge in a 2D grid

In the figure below, cells are labeled row wise, and edges are labeled counter clockwise. For instance, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge ...
1
vote
0answers
14 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
1
vote
1answer
35 views

Is this some kind of hashing?

Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d ...
1
vote
0answers
7 views

Optimal locations for vertices of a polygon with given area [closed]

I want to find the optimal locations for vertices of a polygon (with area A) such that it is as close as possible to the desired area A'. Please note that the vertices need not be fixed at their ...
1
vote
0answers
21 views

Optimal bounding boxes selection for $N$ rectangles

Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into ...
1
vote
3answers
210 views

Closest pair of points in a Plane

I want to write an algorithm to find the closest pair of points among n points in an XY-plane. I have the following approach in my mind: Find the minimum x co-ordinate(minX) and minimum y(minY) ...
6
votes
1answer
66 views

How to find several rectangles with minimum area to cover the red cells

In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) ...
0
votes
2answers
42 views

What is an upright rectangle?

What is an upright rectangle? I came across the phrase in my homework - "The bounding box of a set of S points is the smallest upright rectangle containing S. Describe and analyze an algorithm to ...
2
votes
0answers
43 views

Footprint finding algorithm

I'm trying to come up with an algorithm to optimize the shape of a polygon (or multiple polygons) to maximize the value contained within that shape. I have data with 3 columns: X: the location of ...
2
votes
1answer
33 views

Is there an algorithm that will fill any shape with points a given distance away from each other?

I would like to know if there is an algorithm that if I give a 2D polygon it will give me a set of 2D points. More specifically, those points should have M neighbors that are D apart. The shape is ...
2
votes
0answers
26 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
votes
1answer
53 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 ...
4
votes
1answer
43 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 ...
6
votes
1answer
44 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 ...
6
votes
2answers
64 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 ...
5
votes
1answer
41 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}} ...
2
votes
2answers
61 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. ...
2
votes
1answer
71 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 ...
6
votes
1answer
61 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 ...
0
votes
0answers
38 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 ...
6
votes
1answer
605 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 ...
3
votes
1answer
77 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 ...
2
votes
0answers
24 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 ...
5
votes
1answer
68 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 ...
1
vote
0answers
236 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 ...
1
vote
1answer
73 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 ...
5
votes
1answer
64 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 ...
4
votes
3answers
105 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 ...
4
votes
1answer
40 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 ...
6
votes
2answers
72 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 + ...
1
vote
1answer
42 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 ...
1
vote
1answer
59 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 ...
5
votes
1answer
82 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 ...
3
votes
1answer
59 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 ...
0
votes
0answers
72 views

kd-tree for triangular range queries

Any Ideas for a linear size data structure that can answer triangular range queries, but only for triangles whose edges are either horizontal, vertical, or have slope +1 or −1. It's queries should ...
0
votes
0answers
55 views

Polygon casting - Removing from mold by rotation

How can I show that the problem of finding a center of rotation that allows us to remove P with a single rotation from its mold can be reduced to the problem of finding a point in the common ...
1
vote
1answer
75 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 ...
7
votes
2answers
132 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 ...
2
votes
1answer
16 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 ...
12
votes
0answers
135 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)$ ...
0
votes
0answers
15 views

Divide a polygon into smaller polygons based on some given diagonals

Given a simple polygon(with vertices in counter-clockwise order) and some valid diagonals for that polygon can someone suggest me an algorithm regarding, how to partition the given polygon into ...
7
votes
1answer
96 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 ...
0
votes
0answers
22 views

Centroid of a shape from its boundary

It is possible to find the centroid of a shape from its boundary just by using the average of its boundary points in terms of x,y? http://www.ijmlc.org/papers/251-L30059.pdf
1
vote
1answer
94 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 ...
2
votes
0answers
36 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 ...
1
vote
0answers
28 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 ...
4
votes
1answer
30 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 ...
5
votes
2answers
217 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 ...