@inproceedings{LueckeMossakowski10,
  abstract = {In the area of qualitative spatial reasoning, the LR calculus is a
  quite simple constraint calculus that forms the core of several
  orientation calculi like the dipole calculi and the OPRA-1
  calculus.

  For many qualitative spatial calculi, algebraic closure is applied
  as standard polynomial time decision procedure. For a long time it
  was believed that this can decide the consistency of scenarios of
  the quite simple and basic LR calculus (a refinement of Ligozat's
  flip-flop calculus). However, L{\"u}cke et al. showed that algebraic
  closure is a quite bad approximation of consistency of LR scenarios:
  scenarios in the base relations "Left" and "Right" are always
  algebraically closed. So algebraic closure is completely useless
  here.  Furthermore, Wolter and Lee   have proved that the consistency
  problem for any calculus with relative orientation containing the
  relations "Left" and "Right" is NP-hard.

  In this paper we propose a new polynomial time approximation
  procedure for this NP-hard problem. It is based on the angles of
  triangles in the Euclidean plane. LR scenarios are translated to
  sets of linear inequations over the real numbers. We evaluate the
  quality of this procedure by comparing it both to the old
  approximation using algebraic closure and to the (exact but
  exponential time) Buchberger algorithm for Gr{\"o}bner bases.
},
  added-at = {2016-08-05T15:59:03.000+0200},
  author = {L{\"u}cke, Dominik and Mossakowski, Till},
  biburl = {https://www.bibsonomy.org/bibtex/24633bd7852ca2d8f1f8232e13ea2bd48/tillmo},
  booktitle = {Proceedings of the 5th Starting AI Researcher Symposium (STAIRS 2010)},
  editor = {Gomez-Perez, A. and Agotnes, T.},
  interhash = {bc32414136ad2597bfff65cb25354cac},
  intrahash = {4633bd7852ca2d8f1f8232e13ea2bd48},
  keywords = {calculus consistency qualitative},
  pages = {175-185},
  pdfurl = {http://www.informatik.uni-bremen.de/~till/papers/stairs2010.pdf},
  publisher = {IOS Press; Amsterdam; http://www.iospress.nl},
  series = {Frontiers in Artificial Intelligence and Applications},
  status = {Reviewed},
  timestamp = {2016-08-05T15:59:03.000+0200},
  title = {A much better polynomial time approximation of consistency in the LR calculus},
  url = {http://www.booksonline.iospress.nl/Content/View.aspx?piid=18909},
  volume = 222,
  year = 2010
}