George B. Purdy

  1. A Bichromatic Incidence Bound and an Application to Determined Planes.

    Authors: George B. Purdy, Justin W. Smith, Ben D. Lund
    Subjects: Combinatorics
    Abstract

    We prove that there are $O(m^{2/3}k^{2/3}n^{(d-2)/3} + kn^{d-2})$ incidences
    between $k$ red points and $m$ hyperplanes that are determined jointly by the
    red points and $n-k$ blue points. This is a generalization of an incidence
    bound proved by Agarwal and Aronov \cite{AA92} (i.e., when $k=n$). We provide
    an explicit construction that attains the asymptotic result, showing that the
    bound is tight.

  2. On Finding Ordinary or Monochromatic Intersection Points.

    Authors: George B. Purdy, Justin W. Smith
    Subjects: Computational Geometry
    Abstract

    An algorithm is demonstrated that finds an ordinary intersection in an
    arrangement of $n$ lines in $\mathbb{R}^2$, not all parallel and not all
    passing through a common point, in time $O(n \log{n})$. The algorithm is then
    extended to find an ordinary intersection among an arrangement of hyperplanes
    in $\mathbb{R}^d$, no $d$ passing through a line and not all passing through
    the same point, again, in time $O(n \log{n})$.

    Two additional algorithms are provided that find an ordinary or monochromatic
    intersection, respectively, in an arrangement of pseudolines in time $O(n^2)$.

RSS-материал