Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

4
votes
1answer
34 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
14 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 ...
4
votes
1answer
573 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 ...
2
votes
1answer
59 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 ...
1
vote
0answers
15 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
52 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
210 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
36 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 ...
4
votes
1answer
54 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
78 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 ...
3
votes
1answer
36 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 ...
5
votes
2answers
49 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 + ...
0
votes
1answer
38 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
57 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
77 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
56 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
45 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
51 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
61 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
116 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 ...
1
vote
1answer
15 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 ...
10
votes
0answers
126 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
11 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
85 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
21 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
93 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
33 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
27 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 ...
5
votes
2answers
110 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 ...
3
votes
0answers
41 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 ...
9
votes
2answers
137 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 ...
2
votes
2answers
77 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 ...
3
votes
1answer
123 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 ...
1
vote
1answer
29 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 ...
2
votes
1answer
46 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 ...
4
votes
1answer
47 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 ...
1
vote
3answers
82 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, ...
1
vote
0answers
20 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
vote
0answers
22 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 ...
0
votes
1answer
37 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 ...
7
votes
1answer
129 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
1answer
97 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 ...
3
votes
3answers
81 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 ...
1
vote
1answer
41 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 ...
2
votes
1answer
22 views

Fundamental and essential matrices, value of intrinsic parameters

I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I ultimately want to do is to use information of image i1 and image2 simultaneously, e.g., for ...
0
votes
1answer
38 views

Bringing images into alignment

I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I now want is to bring i1 and i2 into alignment, that is I want to know where pixel (x,y) in i1 is ...
1
vote
1answer
52 views

Merging of two convex polygon chains in O(log n)

Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the ...
4
votes
2answers
131 views

Encircling randomly distributed points

I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will ...
-1
votes
1answer
179 views

Computing the number of squares which are intersected by a line internally

There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only ...
0
votes
2answers
31 views

“Practical” bounding box?

For the sake of simplicity, lets say I have a bunch of 2d points, each have X and Y. The points are distributed somewhat randomly but not completely, they will be biased to be closer to the world ...