1 Search Results for "Milenkovic, Victor"


Document
Table Based Detection of Degenerate Predicates in Free Space Construction

Authors: Victor Milenkovic, Elisha Sacks, and Nabeel Butt

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)


Abstract
The key to a robust and efficient implementation of a computational geometry algorithm is an efficient algorithm for detecting degenerate predicates. We study degeneracy detection in constructing the free space of a polyhedron that rotates around a fixed axis and translates freely relative to another polyhedron. The structure of the free space is determined by the signs of univariate polynomials, called angle polynomials, whose coefficients are polynomials in the coordinates of the vertices of the polyhedra. Every predicate is expressible as the sign of an angle polynomial f evaluated at a zero t of an angle polynomial g. A predicate is degenerate (the sign is zero) when t is a zero of a common factor of f and g. We present an efficient degeneracy detection algorithm based on a one-time factoring of every possible angle polynomial. Our algorithm is 3500 times faster than the standard algorithm based on greatest common divisor computation. It reduces the share of degeneracy detection in our free space computations from 90% to 0.5% of the running time.

Cite as

Victor Milenkovic, Elisha Sacks, and Nabeel Butt. Table Based Detection of Degenerate Predicates in Free Space Construction. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{milenkovic_et_al:LIPIcs.SoCG.2018.61,
  author =	{Milenkovic, Victor and Sacks, Elisha and Butt, Nabeel},
  title =	{{Table Based Detection of Degenerate Predicates in Free Space Construction}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.61},
  URN =		{urn:nbn:de:0030-drops-87749},
  doi =		{10.4230/LIPIcs.SoCG.2018.61},
  annote =	{Keywords: free space construction, degenerate predicates, robustness}
}
  • Refine by Author
  • 1 Butt, Nabeel
  • 1 Milenkovic, Victor
  • 1 Sacks, Elisha

  • Refine by Classification

  • Refine by Keyword
  • 1 degenerate predicates
  • 1 free space construction
  • 1 robustness

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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