--- title: Maximizing Distance on a Square: Turning Geometry into a... description: Discussion about "Maximizing Distance on a Square: Turning Geometry into a Linear Problem" on daily.dev - join the developer community canonical: https://daily.dev/posts/maximizing-distance-on-a-square-turning-geometry-into-a-linear-problem-c8psehuj9 twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: Maximizing Distance on a Square: Turning Geometry into a Linear Problem | daily.dev og:description: Discussion about "Maximizing Distance on a Square: Turning Geometry into a Linear Problem" on daily.dev - join the developer community og:url: https://daily.dev/posts/maximizing-distance-on-a-square-turning-geometry-into-a-linear-problem-c8psehuj9 og:image: https://api.daily.dev/og/posts/c8pSEHUJ9.png og:image:alt: Maximizing Distance on a Square: Turning Geometry into a Linear Problem og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # Maximizing Distance on a Square: Turning Geometry into a Linear Problem **[kavi castelo](https://daily.dev/sources/wxvyslzf6rdtqzq4ugwud)** · [@kavi_castelo](https://daily.dev/kavi_castelo) · 0 upvotes · 0 comments ## Content # Maximizing Distance on a Square: Turning Geometry into a Linear Problem At first glance, this problem looks geometric: points on the boundary of a square, Manhattan distances, and selecting a subset that stays as far apart as possible. But the real trick? This isn’t a 2D geometry problem. It’s a **1D optimization problem in disguise**. Let’s unpack how we transform it—and why that transformation unlocks an efficient solution. --- ## 🔍 Problem Insight We’re given: - A square of side `side` - Points located **only on its boundary** - A requirement to pick `k` points such that the **minimum Manhattan distance between any pair is maximized** This phrasing hints at a classic pattern: > “Maximize the minimum distance” → Think **binary search on the answer** But before we can apply that, we need a structure that allows efficient distance checking. --- ## 🔄 Key Transformation: From 2D → 1D The biggest leap in this problem is realizing: > All boundary points can be mapped to a **single circular line (the square’s perimeter)**. We walk along the square edges in a consistent order and assign each point a **linear coordinate**: ``` if (x === 0) return y; // left edge if (y === side) return side + x; // top edge if (x === side) return side * 3 - y; // right edge return side * 4 - x; // bottom edge ``` This effectively unwraps the square into a **line of length **`4 * side`. Now the problem becomes: > Pick `k` points on a circular line such that the minimum distance between any two is maximized. --- ## 📏 Why This Works Manhattan distance on the square boundary behaves consistently when walking along edges. By mapping points to perimeter positions: - Distance between two points becomes **distance along the perimeter** - But since the shape is circular, we must also consider the **wrap-around gap** This duality is crucial for correctness. --- ## ⚖️ Binary Search on the Answer We now search for the largest minimum distance `d`. Search space: ``` left = 1 right = perimeter / k ``` For each candidate `d`, we ask: > Can we pick `k` points such that every adjacent pair is at least `d` apart? --- ## ✅ Feasibility Check This is where the algorithm gets interesting. ### Step 1: Greedy Placement Start from the first point and repeatedly pick the next valid point using binary search: ``` let j = binarySearch(res, curr + d); ``` This ensures: - Each selected point is at least `d` away from the previous --- ### Step 2: Handle Circular Wrap Even if linear distances look valid, the **first and last points might be too close across the wrap**. We verify: ``` res[last] - res[first] <= perimeter - d ``` If not, we **shift the starting point** and try again. This simulates different “cuts” of the circle into a line. --- ## ⚡ Why Binary Search + Greedy Works This combination works because: - The feasibility function is **monotonic**: - If distance `d` works → smaller distances also work - Greedy ensures we always take the earliest valid option, maximizing future choices --- ## 🧠 Complexity - Sorting: `O(n log n)` - Binary search: `O(log(side))` - Each check: `O(k log n)` Overall: > **O(n log n + log(side) * k log n)** Efficient enough even for large `side` values (up to 1e9). --- ## 💡 Key Takeaways ### 1. Geometry → Linearization Mapping boundary points to a 1D perimeter simplifies everything. ### 2. Circular Constraints Matter Ignoring the wrap-around leads to incorrect solutions. ### 3. Binary Search on Answer A powerful pattern when maximizing minimum values. ### 4. Greedy + Binary Search Synergy Greedy builds candidates; binary search narrows the answer space. --- ## 🧪 Final Thought This problem is a great example of how: > The hardest part isn’t coding—it’s **seeing the right representation**. Once you flatten the square into a line, everything else falls into place. --- ## 📌 Code (Reference) ``` function maxDistance(side: number, points: number[][], k: number): number { const res: number[] = points.map(([x, y]) => { if (x === 0) return y; if (y === side) return side + x; if (x === side) return side * 3 - y; return side * 4 - x; }).sort((a, b) => a - b); const perimeter: number = side * 4; const binarySearch = (arr: number[], target: number): number => { let l = 0, r = arr.length; while (l < r) { let mid = Math.floor((l + r) / 2); if (arr[mid] < target) l = mid + 1; else r = mid; } return l; }; const check = (n: number): boolean => { const m = res.length; let idx: number[] = new Array(k).fill(0); let curr = res[0]; for (let i = 1; i < k; i++) { let j = binarySearch(res, curr + n); if (j === m) return false; idx[i] = j; curr = res[j]; } if (res[idx[k - 1]] - res[0] <= perimeter - n) return true; for (idx[0] = 1; idx[0] < idx[1]; idx[0]++) { for (let j = 1; j < k; j++) { while (idx[j] < m && res[idx[j]] < res[idx[j - 1]] + n) { idx[j]++; } if (idx[j] === m) return false; } if (res[idx[k - 1]] - res[idx[0]] <= perimeter - n) return true; } return false; }; let left = 1, right = Math.floor(perimeter / k) + 1; while (left + 1 < right) { let mid = Math.floor((left + right) / 2); if (check(mid)) left = mid; else right = mid; } return left; } ``` --- If you enjoy problems where **a clever perspective shift turns complexity into simplicity**, this one is worth revisiting. --- [View this post on daily.dev](https://daily.dev/posts/maximizing-distance-on-a-square-turning-geometry-into-a-linear-problem-c8psehuj9) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"DiscussionForumPosting","mainEntityOfPage":"https://daily.dev/posts/maximizing-distance-on-a-square-turning-geometry-into-a-linear-problem-c8psehuj9","headline":"Maximizing Distance on a Square: Turning Geometry into a Linear Problem","text":"Discussion about \"Maximizing Distance on a Square: Turning Geometry into a Linear Problem\" on daily.dev - join the developer community","url":"https://daily.dev/posts/maximizing-distance-on-a-square-turning-geometry-into-a-linear-problem-c8psehuj9","datePublished":"2026-04-25T13:54:42.709Z","dateModified":"2026-04-25T13:54:42.709Z","author":{"@type":"Person","name":"kavi castelo","url":"https://daily.dev/kavi_castelo","image":"https://avatars.githubusercontent.com/u/85213722?v=4","description":"🚀 Engineering the Future | SaaS Architect | Full-Stack Enthusiast | Tech Leader & Innovator","worksFor":{"@type":"Organization","name":"Talentboozt","logo":"https://media.daily.dev/image/upload/s--LIPyJ1-m--/f_auto/v1749208950/companies/talentboozt"},"interactionStatistic":{"@type":"InteractionCounter","interactionType":{"@type":"EndorseAction"},"userInteractionCount":1830}},"image":"https://media.daily.dev/image/upload/s--zcBljXTt--/f_auto/v1777125283/posts/c8pSEHUJ9?_a=BAMAMiWQ0","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"isPartOf":{"@type":"WebPage","url":"https://daily.dev/sources/wxvyslzf6rdtqzq4ugwud","name":"kavi castelo"}} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"kavi castelo","item":"https://daily.dev/sources/wxvyslzf6rdtqzq4ugwud"},{"@type":"ListItem","position":3,"name":"Maximizing Distance on a Square: Turning Geometry into a Linear Problem"}]} ```