Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26476
Titel: New lower bounds for Hopcroft´s problem
Verfasser: Erickson, Jeff
Sprache: Englisch
Erscheinungsjahr: 1994
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set of n points and m hyperplanes in \mathbb{R}^{d}, is any point contained in any hyperplane? We define a general class of partitioning algorithms, and show that in the worst case, for all m and n, any such algorithm requires time \Omega(n\log m+n^{2/3}m^{2/3}+m\log n) in two dimensions, or \Omega(n\log m+n^{5/6}m^{1/2}+n^{1/2}m^{5/6}+m\log n) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcrofts problem in four or more dimensions. Our planar lower bound is within a factor of 2^{O(\log*(n+m))} of the best known upper bound, due to Matousek. Previously, the best known lower bound, in any dimension, was \Omega(n\log m+m\log n). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called a monochromatic cover, and derive lower bounds on the complexity of this representation. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-51801
hdl:20.500.11880/26532
http://dx.doi.org/10.22028/D291-26476
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1994/04
SciDok-Publikation: 5-Apr-2013
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1994_04.pdf30,62 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.