Volume

Dagstuhl Seminar Proceedings, Volume 7212

Publication Details

  • published at: 2007-12-17
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.07212.1
07212 Abstracts Collection – Constraint Databases, Geometric Elimination ang Geographic Information Systems

Authors: Bernd Bank, Max J. Egenhofer, and Bart Kuijpers

Abstract
From 20.05. to 25.05., the Dagstuhl Seminar 07212 ``Constraint Databases, Geometric Elimination and Geographic Information Systems'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Bernd Bank, Max J. Egenhofer, and Bart Kuijpers. 07212 Abstracts Collection – Constraint Databases, Geometric Elimination ang Geographic Information Systems. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{bank_et_al:DagSemProc.07212.1,
  author =	{Bank, Bernd and Egenhofer, Max J. and Kuijpers, Bart},
  title =	{{07212 Abstracts Collection – Constraint Databases, Geometric Elimination ang Geographic Information Systems}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.1},
  URN =		{urn:nbn:de:0030-drops-12870},
  doi =		{10.4230/DagSemProc.07212.1},
  annote =	{Keywords: Constraint databases, geometric elimination, quantier elimination algorithms, geographic information systems}
}
Document
DOI: 10.4230/DagSemProc.07212.2
07212 Manifesto – Constraint Databases, Geometric Elimination ang Geographic Information Systems

Authors: Bernd Bank, Max J. Egenhofer, Joos Heintz, Bart Kuijpers, and Peter Revesz

Abstract
During the last two decades the topic of constraint databases has evolved into a mature area of computer science with sound mathematical foundations and with a profound theoretical understanding of the expressive power of a variety of query languages. Constraint databases are especially suited for applications in which possibly infinite sets of continuous data, that have a geometric interpretation, need to be stored in a computer. Today, the most important application domains of constraint databases are geographic information systems (GIS), spatial databases and spatio-temporal databases. In these applications infinite geometrical sets of continuous data are finitely represented by means of finite combinations of polynomial equality and inequality constraints that describe these data sets (in mathematical terms these geometrical data sets are known as semi-algebraic sets and they have been extensively studied in real algebraic geometry). On the other hand, constraint databases provide us with a new view on classic (linear and nonlinear) optimization theory.
Cite as

Bernd Bank, Max J. Egenhofer, Joos Heintz, Bart Kuijpers, and Peter Revesz. 07212 Manifesto – Constraint Databases, Geometric Elimination ang Geographic Information Systems. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{bank_et_al:DagSemProc.07212.2,
  author =	{Bank, Bernd and Egenhofer, Max J. and Heintz, Joos and Kuijpers, Bart and Revesz, Peter},
  title =	{{07212 Manifesto – Constraint Databases, Geometric Elimination ang Geographic Information Systems}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.2},
  URN =		{urn:nbn:de:0030-drops-12824},
  doi =		{10.4230/DagSemProc.07212.2},
  annote =	{Keywords: Constraint databases, elimination procedures, geographical information systems}
}
Document
DOI: 10.4230/DagSemProc.07212.3
A lower bound for the complexity of linear optimization from a quantifier-elimination point of view

Authors: Rafael Grimson

Abstract
We discuss the impact of data structures in quantifier elimination. We analyze the arithmetic complexity of the feasibility problem in linear optimization theory as a quantifier-elimination problem. For the case of polyhedra defined by $2n$ halfspaces in $mathbb{R}^n$ we prove that, if dense representation is used to code polynomials, any quantifier-free formula expressing the set of parameters describing nonempty polyhedra has size $Omega(4^{n})$.
Cite as

Rafael Grimson. A lower bound for the complexity of linear optimization from a quantifier-elimination point of view. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{grimson:DagSemProc.07212.3,
  author =	{Grimson, Rafael},
  title =	{{A lower bound for the complexity of linear optimization from a quantifier-elimination point of view}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.3},
  URN =		{urn:nbn:de:0030-drops-12837},
  doi =		{10.4230/DagSemProc.07212.3},
  annote =	{Keywords: Quantifier elimination, dense representation, instrinsic, lower bound}
}
Document
DOI: 10.4230/DagSemProc.07212.4
An analytic solution to the alibi query in the bead model for moving object data

Authors: Bart Kuijpers and Walied Othman

Abstract
Moving objects produce trajectories, which are stored in databases by means of finite samples of time-stamped locations. When also speed limitations in these sample points are known, beads can be used to model the uncertainty about the object's location in between sample points. In this setting, a query of particular interest, that has been studied in the literature of geographic information systems (GIS), is the alibi query. This boolean query asks whether two moving objects can have physically met. This adds up to deciding whether the necklaces of beads of these objects intersect. This problem can be reduced to deciding whether two beads intersect. Since, existing software to solve this problem fails to answer this question within a reasonable time, we propose an analytical solution to the alibi query, which can be used to answer the alibi query in constant time, a matter of milliseconds or less, for two single beads and in time proportional to the product of their lengths for necklaces of beads.
Cite as

Bart Kuijpers and Walied Othman. An analytic solution to the alibi query in the bead model for moving object data. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{kuijpers_et_al:DagSemProc.07212.4,
  author =	{Kuijpers, Bart and Othman, Walied},
  title =	{{An analytic solution to the alibi query in the bead model for moving object data}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.4},
  URN =		{urn:nbn:de:0030-drops-12864},
  doi =		{10.4230/DagSemProc.07212.4},
  annote =	{Keywords: Beads, uncertainty, alibi, query, solution, quantifier elimination, constraint database}
}
Document
DOI: 10.4230/DagSemProc.07212.5
Checking the Integrity of Spatial Integrity Constraints

Authors: Stephan Mäs

Abstract
Integrity constraints play a major role when the quality of spatial data is checked by automatic procedures. Nevertheless the possibilities of checking the internal consistency of the integrity constraints themselves are hardly researched jet. This work analyses the applicability of reasoning techniques like the composition of spatial relations and constraint satisfaction in networks of constraints to find conflicts and redundancies in sets of spatial semantic integrity constraints. These integrity rules specify relations among entity classes. Such relations must hold to assure that the data is fitting to the semantics intended by the data model. For spatial data many semantic integrity constraints are based on spatial properties described for example through qualitative topological or metric relations. Since integrity constraints are defined at the class level, the reasoning properties of these spatial relations can not directly be applied. Therefore a set of class relations has been defined which, combined with the instance relations, enables for the specification of integrity constraints and to reason about them.
Cite as

Stephan Mäs. Checking the Integrity of Spatial Integrity Constraints. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{mas:DagSemProc.07212.5,
  author =	{M\"{a}s, Stephan},
  title =	{{Checking the Integrity of Spatial Integrity Constraints}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.5},
  URN =		{urn:nbn:de:0030-drops-12859},
  doi =		{10.4230/DagSemProc.07212.5},
  annote =	{Keywords: Semantic Integrity Constraints, Spatial Relations, Class Level Relations, Reasoning, Consistency of Constraints, Constraint Networks}
}
Document
DOI: 10.4230/DagSemProc.07212.6
Constraint Databases and Geographic Information Systems

Authors: Peter Revesz

Abstract
Constraint databases and geographic information systems share many applications. However, constraint databases can go beyond geographic information systems in efficient spatial and spatiotemporal data handling methods and in advanced applications. This survey mainly describes ways that constraint databases go beyond geographic information systems. However, the survey points out that in some areas constraint databases can learn also from geographic information systems.
Cite as

Peter Revesz. Constraint Databases and Geographic Information Systems. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{revesz:DagSemProc.07212.6,
  author =	{Revesz, Peter},
  title =	{{Constraint Databases and Geographic Information Systems}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.6},
  URN =		{urn:nbn:de:0030-drops-12810},
  doi =		{10.4230/DagSemProc.07212.6},
  annote =	{Keywords: Constraint databases, geographic information systems, moving objects, spatiotemporal data, visualization}
}

Filters

  • Authors
  • B
  • Bank, Bernd
  • E
  • Egenhofer, Max J.
  • G
  • Grimson, Rafael
  • H
  • Heintz, Joos
  • K
  • Kuijpers, Bart
  • M
  • Mäs, Stephan
  • O
  • Othman, Walied
  • R
  • Revesz, Peter

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact