### Top 2 Arxiv Papers Today in Computational Geometry

##### #1. Variations of largest rectangle recognition amidst a bichromatic point set
###### Ankush Acharyya, Minati De, Subhas C. Nandy, Supantha Pandit
Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P=P_r\cup P_b on a plane, where $P_r$ and $P_b$ represent the set of n red points and m blue points respectively, and the objective is to compute a monochromatic object of the desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R^2, (ii) an axis-parallel monochromatic cuboid of maximum size in R^3. The time complexities of the algorithms for problems (i) and (ii) are O(m(m+n)(m\sqrt{n}+m\log m+n \log n)) and O(m^3\sqrt{n}+m^2n\log n), respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree, which was originally invented by J. L. Bentley in 1975. Our in-place variant of the $k$-d tree for a set of n points in R^k supports both orthogonal range reporting and counting query using...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 12721
Unqiue Words: 2372

##### #2. Voronoi diagram of orthogonal polyhedra in two and three dimensions
###### Ioannis Z. Emiris, Christina Katsamaki
Voronoi diagrams are a fundamental geometric data structure for obtaining proximity relations. We consider collections of axis-aligned orthogonal polyhedra in two and three-dimensional space under the max-norm, which is a particularly useful scenario in certain application domains. We construct the exact Voronoi diagram inside an orthogonal polyhedron with holes defined by such polyhedra. Our approach avoids creating full-dimensional elements on the Voronoi diagram and yields a skeletal representation of the input object. We introduce a complete algorithm in 2D and 3D that follows the subdivision paradigm relying on a bounding-volume hierarchy; this is an original approach to the problem. The complexity is adaptive and comparable to that of previous methods, namely linear in the number of sites, namely edges or facets resp. We also provide a numerically stable, open-source implementation in Julia, illustrating the practical nature of our algorithm.
more | pdf | html
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8450
Unqiue Words: 2019

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 129,963 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 129,963 papers.