The Number of Generalized Balanced Lines Article

•  
• Overview
•  
• Research
•  
• Identity
•  
• Additional Document Info
•  
• View All
•  

Overview

abstract

• Let S be a set of r red points and b=r%2b2δ blue points in general position in the plane, with δ≥0. A line ℓ determined by them is balanced if in each open half-plane bounded by ℓ the difference between the number of blue points and red points is δ. We show that every set S as above has at least r balanced lines. The proof is a refinement of the ideas and techniques of Pach and Pinchasi (Discrete Comput. Geom. 25:611-628, 2001), where the result for δ=0 was proven, and introduces a new technique: sliding rotations. © 2010 Springer Science%2bBusiness Media, LLC.

authors

• Orden D.
• Ramos P.
• Salazar Anaya Gelasio

publication date

• 2010-01-01

published in

• Discrete and Computational Geometry  Journal

Research

keywords

• Allowable sequences; Balanced partitions; Circular sequences; Generalized Lower Bound Theorem; Halving triangles; Sliding rotations

Identity

Digital Object Identifier (DOI)

• 10.1007/s00454-010-9253-4

Additional Document Info

start page

• 805

end page

• 811

volume

• 44

issue

• 4