HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Optimal Line Bipartitions of Point Sets

Olivier Devillers 1 Matthew J. Katz
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Let $S$ be a set of $n$ points in the plane. We study the following problem: Partition $S$ by a line into two subsets $S_a$ and $S_b$ such that $max{f(S_a), f(S_b)}$ is minimal, where $f$ is any monotone function defined over $2^S$. We first present a solution to the case where the points in $S$ are the vertices of some convex polygon and apply it to some common cases --- $f(S')$ is the perimeter / area / or width of the convex hull of $S' \subseteq S$ --- to obtain linear solutions (or $O(n\log n)$ solutions if the convex hull of $S$ is not given) to the corresponding problems. This solution is based on an efficient procedure for finding a minimal entry in matrices of some special type / which we believe is of independent interest. For the general case we present a linear space solution which is in some sense output sensitive. It yields solutions to the perimeter and area cases that are never slower and often faster than the best previous solutions.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:49:48 PM
Last modification on : Friday, February 4, 2022 - 3:15:20 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:59:03 PM


  • HAL Id : inria-00073820, version 1



Olivier Devillers, Matthew J. Katz. Optimal Line Bipartitions of Point Sets. RR-2871, INRIA. 1996. ⟨inria-00073820⟩



Record views


Files downloads