betaFeedback

WorksMathematics

Existence of alternating Hamiltonian paths on specific bicolored point sets

Abstract

Consider a bicolored point set PP in general position in the plane consisting of nn blue and nn red points. We show that if PP can be partitioned into bicolored pairs (ai,bi)(a_i,b_i) such that, for every ii, aia_i and bib_i have different colors and the sets P∖{ai}P\setminus \{a_i\} and P∖{bi}P \setminus \{b_i\} have the same order type, then there exists a noncrossing alternating Hamiltonian path on PP. We also investigate the case when PP lies on the circle, and every interval along the circle contains at most cc more points of one color than of the other. For c=2c=2, we show that there exists a noncrossing alternating Hamiltonian path on PP. For c=3c=3, we show that there exist configurations of points for which the longest noncrossing alternating path on PP has size at most (2−1/25)n+O(1)(2-1/25)n + O(1).

Paper details

vlnc:W_dhnxzqf8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…