Fdtxjr

Multi tool use

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.

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

asked Mar 17 at 12:56

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

365

$endgroup$

add a comment | 

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.

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

asked Mar 17 at 12:56

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

365

$endgroup$

add a comment | 

$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.

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

asked Mar 17 at 12:56

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

365

$endgroup$

share|cite|improve this question

asked Mar 17 at 12:56

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

365

share|cite|improve this question

asked Mar 17 at 12:56

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

365

asked Mar 17 at 12:56

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

365

asked Mar 17 at 12:56

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

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

edited Mar 18 at 21:15

answered Mar 17 at 13:22

David KDavid K

55.4k344120

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

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

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

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

Name

Email

Required, but never shown

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

edited Mar 18 at 21:15

answered Mar 17 at 13:22

David KDavid K

55.4k344120

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

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

edited Mar 18 at 21:15

answered Mar 17 at 13:22

David KDavid K

55.4k344120

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  

add a comment | 

$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

edited Mar 18 at 21:15

answered Mar 17 at 13:22

David KDavid K

55.4k344120

$endgroup$

share|cite|improve this answer

edited Mar 18 at 21:15

answered Mar 17 at 13:22

David KDavid K

55.4k344120

answered Mar 17 at 13:22

David KDavid K

55.4k344120

answered Mar 17 at 13:22

David KDavid K

55.4k344120