Rectangle ProblemCovering area algorithm?Rectangular spacing algorithm?How do I prove a combinatorial statement about the change-making problem when using the greedy algorithm?Find coordinates of n points uniformly distributed in a rectangleHow to position rectangles such that they are as close as possible to a reference point but do not overlap?Rectangle over rectangleHow can i fit a specific count of rectangles in a bigger rectangle with a given size?How to divide a large rectangle into N smaller rectanglesFind the number of triangles formed by n lines.Dividing a rectangle into a grid of rectangles/squares

Can I Retrieve Email Addresses from BCC?

Should my PhD thesis be submitted under my legal name?

Is expanding the research of a group into machine learning as a PhD student risky?

Increase performance creating Mandelbrot set in python

Will it be accepted, if there is no ''Main Character" stereotype?

If you attempt to grapple an opponent that you are hidden from, do they roll at disadvantage?

How can I use the arrow sign in my bash prompt?

Personal Teleportation as a Weapon

Tiptoe or tiphoof? Adjusting words to better fit fantasy races

What is the opposite of 'gravitas'?

Is exact Kanji stroke length important?

Valid Badminton Score?

Understanding "audieritis" in Psalm 94

Short story about space worker geeks who zone out by 'listening' to radiation from stars

Is there a problem with hiding "forgot password" until it's needed?

What would be the benefits of having both a state and local currencies?

is this a spam?

How does residential electricity work?

How do I keep an essay about "feeling flat" from feeling flat?

Everything Bob says is false. How does he get people to trust him?

Lay out the Carpet

What defines a dissertation?

Student evaluations of teaching assistants

Can criminal fraud exist without damages?



Rectangle Problem


Covering area algorithm?Rectangular spacing algorithm?How do I prove a combinatorial statement about the change-making problem when using the greedy algorithm?Find coordinates of n points uniformly distributed in a rectangleHow to position rectangles such that they are as close as possible to a reference point but do not overlap?Rectangle over rectangleHow can i fit a specific count of rectangles in a bigger rectangle with a given size?How to divide a large rectangle into N smaller rectanglesFind the number of triangles formed by n lines.Dividing a rectangle into a grid of rectangles/squares













0












$begingroup$


Given A set of Rectangle that are parallel to the X axis.
We should find the most small set of lines that are parallel to the Y axis.
such that each Rectangle will be crossed by at list one line.
For example :
Given a set of 4 Rectangle.



enter image description here



the output will be X = 3 and X = 7.



I was thinking about a greedy algorithm which pass vertical lines to the X axis and If it is crossed with the most number of Rectangles it will enter the line into the group.










share|cite|improve this question









$endgroup$
















    0












    $begingroup$


    Given A set of Rectangle that are parallel to the X axis.
    We should find the most small set of lines that are parallel to the Y axis.
    such that each Rectangle will be crossed by at list one line.
    For example :
    Given a set of 4 Rectangle.



    enter image description here



    the output will be X = 3 and X = 7.



    I was thinking about a greedy algorithm which pass vertical lines to the X axis and If it is crossed with the most number of Rectangles it will enter the line into the group.










    share|cite|improve this question









    $endgroup$














      0












      0








      0





      $begingroup$


      Given A set of Rectangle that are parallel to the X axis.
      We should find the most small set of lines that are parallel to the Y axis.
      such that each Rectangle will be crossed by at list one line.
      For example :
      Given a set of 4 Rectangle.



      enter image description here



      the output will be X = 3 and X = 7.



      I was thinking about a greedy algorithm which pass vertical lines to the X axis and If it is crossed with the most number of Rectangles it will enter the line into the group.










      share|cite|improve this question









      $endgroup$




      Given A set of Rectangle that are parallel to the X axis.
      We should find the most small set of lines that are parallel to the Y axis.
      such that each Rectangle will be crossed by at list one line.
      For example :
      Given a set of 4 Rectangle.



      enter image description here



      the output will be X = 3 and X = 7.



      I was thinking about a greedy algorithm which pass vertical lines to the X axis and If it is crossed with the most number of Rectangles it will enter the line into the group.







      algorithms






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Mar 17 at 12:56









      נירייב שמואלנירייב שמואל

      365




      365




















          1 Answer
          1






          active

          oldest

          votes


















          1












          $begingroup$

          Try your greedy algorithm on this example:



          Using the notation $(a,b)$ for a rectangle whose vertices have $x$-coordinates $a$ or $b,$ consider a set of six rectangles, $(0,2),$ $(0,6),$ $(0,7),$ $(3,10),$ $(4,10),$ and $(8,10).$



          The greatest number of rectangles you can intersect with the first line is four, with a line between $x=4$ and $x=6.$ You then require two more lines to intersect the remaining rectangles. But the entire set can be done with just two lines.




          In this example, the "greatest number of rectangles" algorithm fails because it picks a line in the middle of the figure, leaving some uncrossed rectangles on the left and some uncrossed rectangles on the right, requiring (too many) additional lines on both the left and right.
          You might consider trying to find the leftmost line of your minimal set of lines instead. (By symmetry, if that works, you can just as easily find the rightmost line instead.)






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            So how do I need to change my greedy algorithm?
            $endgroup$
            – נירייב שמואל
            Mar 18 at 18:15











          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "69"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3151512%2frectangle-problem%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          1












          $begingroup$

          Try your greedy algorithm on this example:



          Using the notation $(a,b)$ for a rectangle whose vertices have $x$-coordinates $a$ or $b,$ consider a set of six rectangles, $(0,2),$ $(0,6),$ $(0,7),$ $(3,10),$ $(4,10),$ and $(8,10).$



          The greatest number of rectangles you can intersect with the first line is four, with a line between $x=4$ and $x=6.$ You then require two more lines to intersect the remaining rectangles. But the entire set can be done with just two lines.




          In this example, the "greatest number of rectangles" algorithm fails because it picks a line in the middle of the figure, leaving some uncrossed rectangles on the left and some uncrossed rectangles on the right, requiring (too many) additional lines on both the left and right.
          You might consider trying to find the leftmost line of your minimal set of lines instead. (By symmetry, if that works, you can just as easily find the rightmost line instead.)






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            So how do I need to change my greedy algorithm?
            $endgroup$
            – נירייב שמואל
            Mar 18 at 18:15
















          1












          $begingroup$

          Try your greedy algorithm on this example:



          Using the notation $(a,b)$ for a rectangle whose vertices have $x$-coordinates $a$ or $b,$ consider a set of six rectangles, $(0,2),$ $(0,6),$ $(0,7),$ $(3,10),$ $(4,10),$ and $(8,10).$



          The greatest number of rectangles you can intersect with the first line is four, with a line between $x=4$ and $x=6.$ You then require two more lines to intersect the remaining rectangles. But the entire set can be done with just two lines.




          In this example, the "greatest number of rectangles" algorithm fails because it picks a line in the middle of the figure, leaving some uncrossed rectangles on the left and some uncrossed rectangles on the right, requiring (too many) additional lines on both the left and right.
          You might consider trying to find the leftmost line of your minimal set of lines instead. (By symmetry, if that works, you can just as easily find the rightmost line instead.)






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            So how do I need to change my greedy algorithm?
            $endgroup$
            – נירייב שמואל
            Mar 18 at 18:15














          1












          1








          1





          $begingroup$

          Try your greedy algorithm on this example:



          Using the notation $(a,b)$ for a rectangle whose vertices have $x$-coordinates $a$ or $b,$ consider a set of six rectangles, $(0,2),$ $(0,6),$ $(0,7),$ $(3,10),$ $(4,10),$ and $(8,10).$



          The greatest number of rectangles you can intersect with the first line is four, with a line between $x=4$ and $x=6.$ You then require two more lines to intersect the remaining rectangles. But the entire set can be done with just two lines.




          In this example, the "greatest number of rectangles" algorithm fails because it picks a line in the middle of the figure, leaving some uncrossed rectangles on the left and some uncrossed rectangles on the right, requiring (too many) additional lines on both the left and right.
          You might consider trying to find the leftmost line of your minimal set of lines instead. (By symmetry, if that works, you can just as easily find the rightmost line instead.)






          share|cite|improve this answer











          $endgroup$



          Try your greedy algorithm on this example:



          Using the notation $(a,b)$ for a rectangle whose vertices have $x$-coordinates $a$ or $b,$ consider a set of six rectangles, $(0,2),$ $(0,6),$ $(0,7),$ $(3,10),$ $(4,10),$ and $(8,10).$



          The greatest number of rectangles you can intersect with the first line is four, with a line between $x=4$ and $x=6.$ You then require two more lines to intersect the remaining rectangles. But the entire set can be done with just two lines.




          In this example, the "greatest number of rectangles" algorithm fails because it picks a line in the middle of the figure, leaving some uncrossed rectangles on the left and some uncrossed rectangles on the right, requiring (too many) additional lines on both the left and right.
          You might consider trying to find the leftmost line of your minimal set of lines instead. (By symmetry, if that works, you can just as easily find the rightmost line instead.)







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Mar 18 at 21:15

























          answered Mar 17 at 13:22









          David KDavid K

          55.4k344120




          55.4k344120











          • $begingroup$
            So how do I need to change my greedy algorithm?
            $endgroup$
            – נירייב שמואל
            Mar 18 at 18:15

















          • $begingroup$
            So how do I need to change my greedy algorithm?
            $endgroup$
            – נירייב שמואל
            Mar 18 at 18:15
















          $begingroup$
          So how do I need to change my greedy algorithm?
          $endgroup$
          – נירייב שמואל
          Mar 18 at 18:15





          $begingroup$
          So how do I need to change my greedy algorithm?
          $endgroup$
          – נירייב שמואל
          Mar 18 at 18:15


















          draft saved

          draft discarded
















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3151512%2frectangle-problem%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          How should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer

          random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

          Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye