62
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Planar Visibility Counting

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k<n is an arbitrary parameter. We describe an implementation of this approach and demonstrate the practical benefit of the parameter k to trade memory for query time in an empirical evaluation on three classes of benchmark scenes.

          Related collections

          Most cited references11

          • Record: found
          • Abstract: not found
          • Article: not found

          On a class of O(n2) problems in computational geometry

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Filtering Search: A New Approach to Query-Answering

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              An Output-Sensitive Algorithm for Computing Visibility Graphs

                Bookmark

                Author and article information

                Journal
                30 September 2008
                2009-02-05
                Article
                0810.0052
                001e430b-1c01-44c4-8eec-0c837b782394

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                added Section 4: Implementation and Empirical Evaluation
                cs.CG cs.DS

                Comments

                Comment on this article