On the generation of topological (nk)-configurations

Jürgen Bokowski; Vincent Pilaud

On the generation of topological (n_k)-configurations

Jürgen Bokowski
, Vincent Pilaud

Technische Universität Darmstadt
Laboratoire de Probabilités et Modèles Aléatoires

Résultats de recherche: Contribution à une conférence › Papier › Revue par des pairs

Résumé

An (n_k)-configuration is a set of n points and n lines in the projective plane such that the point { line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n _k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n _k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.

langue originale	Anglais
état	Publié - 1 déc. 2011
Modification externe	Oui
Evénement	23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada Durée: 10 août 2011 → 12 août 2011

Une conférence

Une conférence	23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Pays/Territoire	Canada
La ville	Toronto, ON
période	10/08/11 → 12/08/11

Contient cette citation

@conference{d052701068334b74a73c717b6b78b162,

title = "On the generation of topological (nk)-configurations",

abstract = "An (nk)-configuration is a set of n points and n lines in the projective plane such that the point \{ line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.",

author = "J{\"u}rgen Bokowski and Vincent Pilaud",

year = "2011",

month = dec,

day = "1",

language = "English",

note = "23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 ; Conference date: 10-08-2011 Through 12-08-2011",

}

TY - CONF

T1 - On the generation of topological (nk)-configurations

AU - Bokowski, Jürgen

AU - Pilaud, Vincent

PY - 2011/12/1

Y1 - 2011/12/1

N2 - An (nk)-configuration is a set of n points and n lines in the projective plane such that the point { line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.

AB - An (nk)-configuration is a set of n points and n lines in the projective plane such that the point { line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.

M3 - Paper

AN - SCOPUS:84882983669

T2 - 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011

Y2 - 10 August 2011 through 12 August 2011

ER -

On the generation of topological (nk)-configurations

Résumé

Une conférence

Empreinte digitale

Contient cette citation

On the generation of topological (n_k)-configurations