1
$\begingroup$

I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally:

Let:

  • $P$ be a polygon consisting of points $\{x_1,x_2,...x_n,x_1\}$
  • $S$ be a subset of $P$, bounded by points $x_j$ and $x_k$:
  • $m$ be a number of extra points we can allocate

Then, we want to minimize the area of $P$, using the following means:

  • modifying the position of points $\{x_{j+1},...,x_{k-1}\}$
  • adding new points to the interval $(x_j,x_k)$

Here is a very example for $m =1$ (notice that the boundary points $x_j$ and $x_k$ aren't subject to being modified)

enter image description here

So far, the best I can do is a bruteforce solution. Basically try moving the point around in some discrete increments into various directions, then check if it makes sense (see that it does not create intersections within the polygon), and calculate the area. After that, I check which direction gave the best area, and I continue the process again until the area converges.

Obviously this is a flawed solution in that:

  • It does not guarantee anything, it is just trial and error

  • It is extremely computationally expensive

  • It gives rise to certain anomalies

My question is, could there possibly be a better approach, maybe even one that would guarantee an exact solution in polynomial time?

$\endgroup$

1 Answer 1

0
$\begingroup$

Try all possibilities for vertices $P,Q,R,S$ where $P,Q$ are adjacent and $R,S$ are adjacent (there are $O(n^2)$ possibilities). For each such possibility, find the best way to add a point $T$ after $P$ and before $Q$, such that $T$ falls on the line segment $RS$. This involves finding a point $T$ on the line segment $RS$ that maximizes the area of the triangle $PTQ$. You should be able to do that in $O(1)$ time. Repeat for each possible $P,Q,R,S$ and take the best one found. This should yield an $O(n^2)$ time algorithm.

I don't know if it is possible to do better than $O(n^2)$ time.

$\endgroup$
2
  • $\begingroup$ This only works for convex polygons, which is not my case, but it helped me a lot when devising the solution - thainks! $\endgroup$
    – user129186
    Nov 25, 2018 at 0:05
  • $\begingroup$ @user129186, glad it was helpful! Can I encourage you to take the time to write an answer explaining your solution for arbitrary (not necessarily) convex polygons? That would be a nice contribution! $\endgroup$
    – D.W.
    Nov 25, 2018 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.