0
$\begingroup$

enter image description here

I've included an example of one such orthogonal pyramid. I would like to find a way to prove that this orthogonal pyramid can be partitioned by diagonals into convex quadrilaterals, and do so with an algorithm in linear time. My understanding is that a sweep-line algorithm from top to bottom would work well. However, I am not quite sure how to proceed with it.

Some additional info: An orthogonal polygon is a polygon in which each pair of adjacent edges meets orthogonally. An orthogonal pyramid (like the one pictured above) is an orthogonal polygon monotone with respect to the vertical that contains one horizontal edge (h in our case above) whose length is the sum of the lengths of all the other horizontal edges.

$\endgroup$
  • $\begingroup$ Can you provide a self-contained definition of what an "orthogonal pyramid" is, and what it means to "partition it by diagonals"? I don't think a picture or example is enough to clearly define those concepts (at least, it isn't for me). Also, what have you tried? Have you tried working through some small examples? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 16 '17 at 20:21
  • $\begingroup$ Partitioning by diagonals would mean that we're trying to decompose P into convex quadrilaterals by only introducing diagonals onto the pyramid above. $\endgroup$ – montagne Mar 16 '17 at 20:36
  • 1
    $\begingroup$ Googling "orthogonal pyramid partitioned by diagonal" immediately finds a link to a resource that appears to describe a solution to this problem. I encourage you to be more resourceful and search before asking, and try to solve the problem yourself before asking, and show what approaches you've tried and why you rejected them. $\endgroup$ – D.W. Mar 16 '17 at 20:41
  • $\begingroup$ Is a diagonal allowed to be horizontal? $\endgroup$ – Angela Richardson Mar 18 '17 at 18:45
  • $\begingroup$ @D.W. Excuse me... I'm looking for the answer to the same question that OP asked. But googling "..." does not work. On the other hand, the question is about "orthogonal pyramids", not "orthogonal polygons". I mean the question is much easier. we do not want to propose a way of paritioning ALL orthogonal polygons. $\endgroup$ – Arman Malekzadeh Oct 19 '18 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.