Questions algorithmic solutions of geometric problems.

learn more… | top users | synonyms

3
votes
3answers
40 views

Is there an efficient algorithm to extract the farthest ends of a thin contour?

Let's say you have pixel bitmaps that look something like this: From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the ...
5
votes
0answers
56 views

Repeated point in polygon: preprocessing complexity given logarithmic query time?

I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is ...
3
votes
1answer
29 views

Snap/Fit a chain of lines to points

I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it. Here is ...
-1
votes
0answers
17 views

Proof of convex combination of two distinct points [migrated]

A convex combination of two vertices p = ( a, b ) and q = ( c, d ) is any point r = ( e, f ) such that for some x in range 0 <= x <= 1, e = xa + ( 1 - x )c and f = xb + ( 1 - x )d. Intuitively, ...
1
vote
1answer
28 views

Red-blue intersection requirements

In the red-blue line segments intersection problem, what does it mean that the red-red (and blue-blue) lines cannot intersect? Does mean mean that the algorithms wont work correctly or does it mean ...
3
votes
0answers
59 views

Find internal surfaces in an oriented mesh

I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union ...
1
vote
1answer
64 views

smallest circle that covers two points with its center in x axis

I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know ...
0
votes
1answer
62 views

Voronoi Diagram: Exactly 2n-5 vertices

I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices. I tried to use the Euler ...
3
votes
1answer
96 views

Convex hull algorithm in $O(\min(mn, n\log n))$

I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$. My first guess was ...
4
votes
0answers
34 views

Computing the right tangent of two convex hulls

My question deals with the algorithm of computing the convex hull in 2D by Preparata. Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex ...
1
vote
0answers
33 views

Voronoi Diagram Question

I am stuck on that question, it's about Voronoi diagrams Show that for some set of $n$ points, there can be $\Omega(n^2)$ intersections between the edges of the Voronoi diagram and the edges of ...
0
votes
1answer
27 views

Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$. When would one use a norm other than $L^2$ in a $k$-$d$ tree?
3
votes
1answer
102 views

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 $(x_i,...
1
vote
2answers
94 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 $O\left(n^{2-\...
0
votes
1answer
79 views

Find cell neighbors of a given edge in a 2D grid [closed]

In the figure below, cells are labeled row wise, and edges are labeled counter clockwise. That is, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge #7, ...
1
vote
0answers
18 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
37 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
9 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
23 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
221 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) co-...
6
votes
1answer
85 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) and ...
0
votes
2answers
63 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
47 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
38 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
27 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
45 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
49 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
73 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$...
5
votes
1answer
42 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
70 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. ...
3
votes
1answer
90 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
65 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
68 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
608 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
91 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
84 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
246 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\...
1
vote
1answer
99 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
73 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
138 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
48 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
84 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
43 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 $x'$ ...
5
votes
1answer
90 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
61 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
83 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
56 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 ...